Problem H
Longest Life

Illustration by William Ely Hill

Everyone wants to live as long a life as possible. As time progresses, technology progresses. Various anti-aging pills get introduced to the market at various times which allow a person to age more slowly than normal. In particular, an $x$-$y$ pill, when taken regularly, ages your body only $y$ seconds over the course of $x$ seconds. So, if you took a $100$-$87$ pill regularly, then over the next $100$ seconds, your body would only age $87$ seconds. You can only take one of these pills at a time (or none at all). The only downside to using one of these pills is that due to the change in regimen, if you switch to a pill, it automatically ages you $c$ seconds. The value of $c$ is the same for all pills.

Any time you switch to an $x$-$y$ pill, you can take it for any number of seconds, but you can only switch to a pill at or after the time it first becomes available on the market. For the purposes of this problem assume that your life starts at time $t = 0$ seconds and that without the aid of any pills, you would live to be $n$ seconds old.

Given information about each different pill introduced into the market (the time it is introduced, in seconds, and its corresponding $x$ and $y$ values as previously described) and $c$, the number of seconds you automatically age when switching pills (or switching to a pill from no pill at all), determine the longest you can live, over all possible schedule of pills you could take.

Input

The first line of input consists of three positive integers, $n$ ($n \le 3\cdot 10^9$), representing the number of seconds you would live without taking any pills, $p$ ($p \le 10^5$), the number of pills that become available on the market, and $c$ ($c \le 10^5$), the time in seconds you age as soon as you switch to a different pill. $p$ lines follow with the $i^{th}$ line containing three space separated integers: $t_{i}$ $(1 \le t_{i} \le 10^{12})$, $x_{i}$ and $y_{i}$ $(1 \le y_{i} < x_{i} \le 10^{4}$), representing the time the $i^{th}$ pill gets introduced to the market, and the corresponding $x$ and $y$ values for it. In addition, for all $i$, $1 \le i \le n-1$, it is guaranteed that $t_{i+1} - t_{i} > c$.

Output

Output a single real number, representing the maximum number of seconds that you could live, if you take the appropriate pills. Your answer should be correct within a relative or absolute error of $10^{-6}$.

100 3 10
15 99 98
40 3 2
90 10 9

115.000000000

10000 4 100
1000 1001 1000
1994 10 9
2994 100 89
3300 1000 1

6633900.000000000