Problem M
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
Input
The first line contains two integers
Each of the next
The traffic lights will be ordered in increasing order of
Output
Output the time (in seconds) Luka needs to reach the end of the road.
Sample Input 1 | Sample Output 1 |
---|---|
2 10 3 5 5 5 2 2 |
12 |
Sample Input 2 | Sample Output 2 |
---|---|
4 30 7 13 5 14 4 4 15 3 10 25 1 1 |
36 |