[Solution] Late For Work Codeforces Solution

F. Late For Work

time limit per test

3 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

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.

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 1$1$ to 𝑛$n$.

Each traffic light cycles after 𝑡$t$ seconds. The 𝑖$i$-th traffic light is green$\text{green}$ (in which case Harsh can cross the traffic light) for the first 𝑔𝑖$g_i$ seconds, and red$\text{red}$ (in which case Harsh must wait for the light to turn green$\text{green}$) for the remaining (𝑡−𝑔𝑖)$(t-g_i)$ seconds, after which the pattern repeats. Each light's cycle repeats indefinitely and initially, the 𝑖$i$-th light is 𝑐𝑖$c_i$ seconds into its cycle (a light with 𝑐𝑖=0$c_i=0$ has just turned green$\text{green}$). 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 green$\text{green}$ from [0,𝑔𝑖)$[0,g_i)$ and red$\text{red}$ from [𝑔𝑖,𝑡)$[g_i,t)$ (after which it repeats the cycle). The 𝑖$i$-th traffic light is initially at the 𝑐𝑖$c_i$-th second of its cycle.

From the 𝑖$i$-th traffic light, exactly 𝑑𝑖$d_i$ 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

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

 arrives, which can be anywhere between 0$0$ to ∞$\mathrm{\infty }$ seconds from now. Can you tell Harsh the minimum possible amount of time he needs to spend on the road?

Input

The first line of input will contain two integers, 𝑛$n$ and 𝑡$t$ (2≤𝑛≤2⋅105$2\le n\le 2\cdot {10}^5$, 2≤𝑡≤109$2\le t\le {10}^9$) 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 𝑔𝑖$g_i$ and 𝑐𝑖$c_i$ (1≤𝑔𝑖<𝑡$1\le g_i<t$, 0≤𝑐𝑖<𝑡$0\le c_i<t$) describing the 𝑖$i$-th traffic light.

The following line of input contains 𝑛−1$n-1$ integers 𝑑1,𝑑2,…,𝑑𝑛−1$d_1,d_2,\dots ,d_{n-1}$ (0≤𝑑𝑖≤109$0\le d_i\le {10}^9$) — the time taken to travel from the 𝑖$i$-th to the (𝑖+1)$(i+1)$-th traffic light.

Output

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