Longest Life

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. Switching to a pill from no pill at all also ages you $c$ seconds.

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. Your life starts at time $t = 0$ seconds, and without the aid of any pills, you would live to be $n$ seconds old.

You are given the time each pill is introduced to the market, $t_i$ (in seconds), and its $x_i$ and $y_i$ values, along with $c$. Determine the longest you can live over all possible schedules of pills.

The first line contains three positive integers $n$ ($n \le 3 \cdot 10^9$), $p$ ($p \le 10^5$), and $c$ ($c \le 10^5$). Here $n$ is the number of seconds you would live without taking any pills, $p$ is the number of pills that become available on the market, and $c$ is the number of seconds you age as soon as you switch to a different pill. The next $p$ lines each contain three space-separated integers $t_i$, $x_i$, and $y_i$ ($1 \le t_i \le 10^{12}$, $1 \le y_i < x_i \le 10^4$), giving the time the $i$th pill is introduced and its $x$ and $y$ values. For all $i$, $1 \le i \le n-1$, it is guaranteed that $t_{i+1} - t_i > c$.

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