Road and Traffic Lights

Interview

Time limit1sMemory limit128 MB

Summary

Simulate a truck moving at 1 m/s along a road with traffic lights that cycle red then green, waiting at reds, and output total travel time to the end.

Level: Easy3 of 10
Topics: Simulation, Implementation
Solved: No attempts yet

Problem

A driver is driving a truck along a straight road from position 0 meters to position L meters. Several traffic lights are installed on the road.

Each traffic light repeats an infinite cycle: red for R seconds, then green for G seconds. At time 0, when the truck enters the road, every traffic light has just started its red phase.

The truck moves at 1 meter per second. If it reaches a traffic light while that light is red, it stops at that position and waits until the light turns green before continuing.

Compute the total time required for the truck to reach the end of the road.

Input

The first line contains the number of traffic lights N and the road length L. (1 <= N <= 100, 1 <= L <= 1000)

Each of the next N lines contains D, R, and G for one traffic light. D is the distance from the start of the road to the traffic light, R is the duration of the red phase, and G is the duration of the green phase. (1 <= D < L, 1 <= R <= 100, 1 <= G <= 100)

The traffic lights are given in increasing order of D, and no two traffic lights are at the same position.

Output

Print the time, in seconds, required for the truck to reach the end of the road.

Examples2

Example 1
Input
```
2 10
3 5 5
5 2 2
```
Expected output
```
12
```
Example 2
Input
```
4 30
7 13 5
14 4 4
15 3 10
25 1 1
```
Expected output
```
36
```