Riding the Green Wave

A cyclist starts at position 0 at time 0 and rides along a straight road at exactly 1 unit of distance per second, towards the finish at position road_length. Along the road stand traffic lights, given as lights, a list of [position, green, red] triples.

Every light runs the same pattern forever, starting at time 0: green for green seconds, then red for red seconds, then green again, and so on. So a light is green at time t exactly when t % (green + red) < green. When the cyclist reaches a light at time t:

• if the light is green at time t, the cyclist passes without stopping;
• otherwise the cyclist waits and passes at the first later moment the light turns green.

Passing a light takes no time. Write arrival_time(road_length, lights) that returns the time at which the cyclist reaches the finish.

Examples

Input:  road_length = 10, lights = [[3, 2, 3]]
Output: 12
Explanation: at t=3 the light is red (3 % 5 = 3, not below 2). It turns green at t=5.

Input:  road_length = 20, lights = [[4, 5, 5], [10, 3, 2], [15, 1, 1]]
Output: 21

Input:  road_length = 6, lights = [[5, 5, 5]]
Output: 11
Explanation: the light turns red exactly at t=5, the moment the cyclist arrives.

Constraints

• 1 <= road_length <= 10**12
• 0 <= len(lights) <= 10**4
• positions are strictly increasing and 0 < position < road_length
• 1 <= green <= 10**9 and 0 <= red <= 10**9

Goals

• Carry a clock through a list of events
• Use % to find where a repeating cycle currently is
• Jump straight over waiting time instead of ticking second by second