26461번 - Stop & Go 다국어

문제

Mr. Drive, a.k.a. Mr. D, is famous for his thorough safe driving. Not only he always drives a car at an exact legal speed, but also he immediately stops a car if a traffic light turns red from green when he just enters a crossing, and he immediately starts a car at an exact legal speed when a traffic light just turns green from red.

Mr. D's next driving course is a simple straight road with length $L$ and the legal speed limit 1ドル$ per second. Mr.D will start his drive at time 0ドル$. The road has $N$ traffic lights numbered 1ドル$ through $N$. The traffic light $i$ is at a distance of $x_i$ from the start point. At time 0ドル,ドル all the $N$ traffic lights are green. The $i$-th traffic light turns red from green after $g_i$ seconds, then turns green from red after $r_i,ドル and then turns red from green after $g_i$ seconds, then turns green from red after $r_i,ドル and so on.

In this situation, Mr. D will start from the start point and run a car at speed 1ドル$ per second. If the $i$-th traffic light is green or just turns green from red (but not just turns red from green) when Mr. D reaches $x_i,ドル Mr. D won't stop and go through the crossing at speed 1ドル$ per second. If the $i$-th traffic light is red or just turns red from green (but not just turns green from red) when Mr. D reaches $x_i,ドル Mr. D will stop until the $i$-th traffic light turns green.

Your task is to compute the time in seconds when Mr. D reaches point $L,ドル for given $N$ traffic lights.

입력

The first line of the input consists of two integers, the number $N$ (1ドル ≤ N ≤ 100,000円$) of traffic lights on the road and the length $L$ (1ドル ≤ L ≤ 10^9$) of the road. The $i$-th of the following $N$ lines has three integers $x_i,ドル $g_i,ドル and $r_i,ドル where $x_i$ (1ドル ≤ x_i < L$) is the position of the $i$-th traffic light from the start point, $g_i$ (1ドル ≤ g_i ≤ 10^9$) is the duration the $i$-th traffic light is green, and $r_i$ (1ドル ≤ r_i ≤ 10^9$) is the duration the $i$-th traffic light is red. You can assume all the positions of the traffic lights are different. In other words, $x_i \ne x_j$ holds for all $i \ne j$.

출력

Output in a line a single integer, which is the time in seconds when Mr. D reaches point $L$.

제한

힌트