시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 512 MB4412923.077%

문제

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

출처

ICPC > Regionals > North America > North America Qualification Contest > ACM-ICPC North America Qualifier 2018 H번

  • 문제를 만든 사람: Arup Guha