**Late For Work solution codeforces** – Debajyoti has a very important meeting to attend and he is already very late. Harsh, his driver, needs to take Debajyoti to the destination for the meeting as fast as possible.

## [Solution] Late For Work solution codeforces

Harsh needs to pick up Debajyoti from his home and take him to the destination so that Debajyoti can attend the meeting in time. A straight road withĀ šnĀ traffic lights connects the home and the destination for the interview. The traffic lights are numbered in order fromĀ 11Ā toĀ šn.

Each traffic light cycles afterĀ š”tĀ seconds. TheĀ ši-th traffic light isĀ greengreenĀ (in which case Harsh can cross the traffic light) for the firstĀ ššgiĀ seconds, andĀ redredĀ (in which case Harsh must wait for the light to turnĀ greengreen) for the remainingĀ (š”āšš)(tāgi)Ā seconds, after which the pattern repeats. Each light’s cycle repeats indefinitely and initially, theĀ ši-th light isĀ ššciĀ seconds into its cycle (a light withĀ šš=0ci=0Ā has just turnedĀ greengreen). In the case that Harsh arrives at a light at the same time it changes colour, he will obey the new colour.Ā Formally, theĀ ši-th traffic light isĀ greengreenĀ fromĀ [0,šš)[0,gi)Ā andĀ redredĀ fromĀ [šš,š”)[gi,t)Ā (after which it repeats the cycle). TheĀ ši-th traffic light is initially at theĀ ššci-th second of its cycle.

From theĀ ši-th traffic light,Ā exactlyĀ ššdiĀ seconds are required to travel to the next traffic light (that is to theĀ (š+1)(i+1)-th light). Debajyoti’s home is located just before the first light and Debajyoti drops for the interview as soon as he passes theĀ šn-th light. In other words, no time is required to reach the first light from Debajyoti’s home or to reach the interview centre from theĀ šn-th light.

Harsh does not know how much longer it will take for Debajyoti to get ready. While waiting, he wonders what is the minimum possible amount of time he will spend driving provided he starts the moment Debajyoti arrives, which can be anywhere betweenĀ 00Ā toĀ āāĀ seconds from now. Can you tell Harsh the minimum possible amount of time he needs to spend on the road?

## [Solution] Late For Work solution codeforces

The first line of input will contain two integers,Ā šnĀ andĀ š”tĀ (2ā¤šā¤2ā 1052ā¤nā¤2ā 105,Ā 2ā¤š”ā¤1092ā¤tā¤109) denoting the number of traffic lights and the cycle length of the traffic lights respectively.

šnĀ lines of input follow. TheĀ ši-th line will contain two integersĀ ššgiĀ andĀ ššciĀ (1ā¤šš<š”1ā¤gi<t,Ā 0ā¤šš<š”0ā¤ci<t) describing theĀ ši-th traffic light.

The following line of input containsĀ šā1nā1Ā integersĀ š1,š2,ā¦,ššā1d1,d2,ā¦,dnā1Ā (0ā¤ššā¤1090ā¤diā¤109) ā the time taken to travel from theĀ ši-th to theĀ (š+1)(i+1)-th traffic light.

Output a single integerĀ ā the minimum possible amount of time Harsh will spend driving.

5 10 4 2 7 3 3 6 5 2 8 0 1 2 3 4

## [Solution] Late For Work solution codeforces

11

6 9 5 3 5 5 7 0 5 8 7 7 6 6 0 0 0 0 0

3

## [Solution] Late For Work solution codeforces

In the first example, Harsh can do the following:

- Initially, theĀ 55Ā traffic lights are at the following seconds in their cycle:Ā {2,3,6,2,0}{2,3,6,2,0}.
- An optimal time for Harsh to start is if Debajyoti arrives afterĀ 11Ā second. Note that thisĀ 11Ā second will not be counted in the final answer.
- The lights will be now atĀ {3,4,7,3,1}{3,4,7,3,1}, so Harsh can drive from theĀ 11-st light to theĀ 22-nd light, which requiresĀ 11Ā second to travel.
- The lights are now atĀ {4,5,8,4,2}{4,5,8,4,2}, so Harsh can continue driving, without stopping, to theĀ 33-rd light, which requiresĀ 22Ā seconds to travel.
- The lights are now atĀ {6,7,0,6,4}{6,7,0,6,4}, so Harsh continues to theĀ 44-th light, which requiresĀ 33Ā seconds to travel.
- The lights are now atĀ {9,0,3,9,7}{9,0,3,9,7}. Harsh must waitĀ 11Ā second for theĀ 44-th light to turn green before going to theĀ 55-th light, which requiresĀ 44Ā seconds to travel.
- The lights are now atĀ {4,5,8,4,2}{4,5,8,4,2}, so Harsh can continue traveling, without stopping, to the meeting destination. The total time that Harsh had to drive for isĀ 1+2+3+1+4=111+2+3+1+4=11Ā seconds.

In the second example, Harsh can do the following:

- Initially, theĀ 66Ā traffic lights are at the following seconds in their cycle:Ā {3,5,0,8,7,6}{3,5,0,8,7,6}.
- An optimal time for Harsh to start is if Debajyoti arrives afterĀ 11Ā second. Note that thisĀ 11Ā second will not be counted in the final answer.
- The lights will be now atĀ {4,6,1,0,8,7}{4,6,1,0,8,7}, so Harsh can drive from theĀ 11-st light to theĀ 22-nd light, which requiresĀ 00Ā seconds to travel.
- The lights are still atĀ {4,6,1,0,8,7}{4,6,1,0,8,7}. Harsh must waitĀ 33Ā seconds for theĀ 22-nd light to turn green, before going to theĀ 33-rd light, which requiresĀ 00Ā seconds to travel.
- The lights are now atĀ {7,0,4,3,2,1}{7,0,4,3,2,1}, so Harsh continues to theĀ 44-th light, which requiresĀ 00Ā seconds to travel.
- The lights are still atĀ {7,0,4,3,2,1}{7,0,4,3,2,1}, so Harsh continues to theĀ 55-th light, which requiresĀ 00Ā seconds to travel.
- The lights are still atĀ {7,0,4,3,2,1}{7,0,4,3,2,1}, so Harsh continues to theĀ 66-th light, which requiresĀ 00Ā seconds to travel.
- The lights are still atĀ {7,0,4,3,2,1}{7,0,4,3,2,1}, so Harsh can continue traveling, without stopping, to the meeting destination. The total time that Harsh had to drive for isĀ 0+3+0+0+0=30+3+0+0+0=3Ā seconds.