Stop & Go

Interview

Time limit2sMemory limit1024 MB

Summary

Given N traffic lights on a road of length L, find the time Mr. D reaches point L, stopping at each red light he meets.

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

Problem

Mr. Drive, also known as Mr. D, always drives at exactly the legal speed. If a traffic light turns red from green as he enters a crossing, he stops at once. When a light turns green from red, he starts at once and drives at the legal speed.

His next course is a straight road of length $L$ with a legal speed limit of 1 per second. He starts at time 0 from the start point and drives at speed 1 per second. The road has $N$ traffic lights numbered 1 through $N$ . Light $i$ is at distance $x_i$ from the start. At time 0 all lights are green. Light $i$ turns red after $g_i$ seconds of green, turns green again after $r_i$ seconds of red, turns red after another $g_i$ seconds of green, and so on.

When Mr. D reaches $x_i$ , if light $i$ is green or has just turned green from red, he passes at speed 1 without stopping. If light $i$ is red or has just turned red from green, he stops until light $i$ turns green.

Compute the time when Mr. D reaches point $L$ .

Input

The first line has two integers $N$ ( $1 \le N \le 100000$ ) and $L$ ( $1 \le L \le 10^9$ ). Each of the next $N$ lines has three integers $x_i$ , $g_i$ , and $r_i$ ( $1 \le x_i < L$ , $1 \le g_i \le 10^9$ , $1 \le r_i \le 10^9$ ). All positions $x_i$ are distinct.

Output

Print the time in seconds when Mr. D reaches point $L$ , as a single integer.

Examples3

Example 1
Input
```
3 10
3 2 2
6 1 1
9 2 5
```
Expected output
```
15
```
Example 2
Input
```
1 100
50 1000 1
```
Expected output
```
100
```
Example 3
Input
```
3 100
70 10 50
20 10 15
50 50 10
```
Expected output
```
150
```