시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 0 0 0 0.000%

## 문제

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.

## 입력

The first line of input consists of three positive integers, n (n ≤ 3 · 109), representing the number of seconds you would live without taking any pills, p (p ≤ 105), the number of pills that become available on the market, and c (c ≤ 105), the time in seconds you age as soon as you switch to a different pill. p lines follow with the ith line containing three space separated integers: ti (1 ≤ ti ≤ 1012), xi and yi (1 ≤ yi < xi ≤ 104), representing the time the ith pill gets introduced to the market, and the corresponding x and y values for it. In addition, for all i, 1 ≤ i ≤ n − 1, it is guaranteed that ti+1 − ti > c.

## 출력

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.

## 예제 입력 1

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


## 예제 출력 1

115.000000000


## 예제 입력 2

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


## 예제 출력 2

6633900.000000000