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}$.

-----Examples-----
Sample Input:
100 3 10
15 99 98
40 3 2
90 10 9
Sample Output:
115.000000000

见题面

见题面