COCI 2007/2008, Contest #6

Task SEMAFORI

Luka is driving his truck along a long straight road with many traffic lights. For each traffic light he knows how long the red and green lights will be on (the cycle repeating endlessly).

When Luka starts his journey, all traffic lights are red and just started their cycle. Luka moves one distance unit per second. When a traffic light is red, he stops and waits until it turns green.

Write a program that determines how much time Luka needs to reach the end of the road. The start of the road is at distance zero, the end at distance L.

Input

The first line contains two integers N and L (1 ≤ N ≤ 100, 1 ≤ L ≤ 1000), the number of traffic lights on the road and the length of the road.

Each of the next N lines contains three integers D, R and G, describing one traffic light (1 ≤ D < L, 1 ≤ R ≤ 100, 1 ≤ G ≤ 100). D is the distance of the traffic light from the start of the road. R and G denote how long the red and green lights are on, respectively.

Output

Output the time (in seconds) Luka needs to reach the end of the road.

Examples

2 10
3 5 5
5 2 2

12

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

36

In the first example, Luka will wait 2 seconds at the first traffic light. After that he will reach the second traffic light while it is green and be able to pass through immediately.

All Submissions
Best Solutions

Point Value: 7
Time Limit: 1.00s
Memory Limit: 32M
Added: Aug 05, 2013

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)