Problem Description

Luka is driving a truck, and there are $n$ traffic lights on the road.

For each traffic light, he knows how long the red light and the green light stay on (repeating in a cycle).

When Luka starts driving, all traffic lights are red and their cycles start at the same time.

Luka moves $1$ unit of distance per second. When a traffic light is red, he must stop and wait until it turns green.

Write a program to determine how much time Luka needs to reach the end of the road.

The start of the road is at $0$, and the end is at $l$.

Input Format

The first line contains two integers $n, l$, which represent the number of traffic lights and the length of the road.

Each of the next $n$ lines contains three integers $d, r, g$. $d$ is the distance from the traffic light to the start of the road, and $r$ and $g$ are the durations of the red and green lights.

The traffic lights are given in increasing order of $d$.

No two traffic lights are at the same position.

Output Format

The first line contains one positive integer, which is the time Luka needs to reach the end of the road.

2 10
3 5 5
5 2 2 

12

4 30
7 13 5
14 4 4
15 3 10
25 1 1 

36

Hint

Sample #1 Explanation

In the first sample, Luka waits $2$ seconds at the first traffic light. Then he reaches the second traffic light, which is green, so he can pass immediately.

Constraints

For $100\%$ of the testdata, $1 \le n \le 100$, $1 \le l \le 10^3$, $1 \le d < l$, $1 \le r \le 100$, $1 \le g \le 100$.

Notes

• This problem is worth $30$ points in total.
• This problem enables the O2 optimization switch by default.
• The problem is translated from COCI2007-2008 CONTEST #6 T2 SEMAFORI, translated by
  https://www.luogu.com.cn/user/219791

Translated by ChatGPT 5