시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB46322668.421%

문제

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

예제 입력 1

3 10
3 2 2
6 1 1
9 2 5

예제 출력 1

15

예제 입력 2

1 100
50 1000 1

예제 출력 2

100

예제 입력 3

3 100
70 10 50
20 10 15
50 50 10

예제 출력 3

150