Description

Input

The first line of input will contain two integers, $n$ and $t$ ($2 \le n \le 2 \cdot 10^5$, $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 \le g_i < t$, $0 \le c_i < t$) describing the $i$-th traffic light.

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

Output

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

11

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

3

Note

In the first example, Harsh can do the following:

• Initially, the $5$ traffic lights are at the following seconds in their cycle: $\{2,3,6,2,0\}$.
• An optimal time for Harsh to start is if Debajyoti arrives after $1$ second. Note that this $1$ second will not be counted in the final answer.
• The lights will be now at $\{3,4,7,3,1\}$, so Harsh can drive from the $1$-st light to the $2$-nd light, which requires $1$ second to travel.
• The lights are now at $\{4,5,8,4,2\}$, so Harsh can continue driving, without stopping, to the $3$-rd light, which requires $2$ seconds to travel.
• The lights are now at $\{6,7,0,6,4\}$, so Harsh continues to the $4$-th light, which requires $3$ seconds to travel.
• The lights are now at $\{9,0,3,9,7\}$. Harsh must wait $1$ second for the $4$-th light to turn green before going to the $5$-th light, which requires $4$ seconds to travel.
• The lights are now at $\{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=11$ seconds.

In the second example, Harsh can do the following:

• Initially, the $6$ traffic lights are at the following seconds in their cycle: $\{3,5,0,8,7,6\}$.
• An optimal time for Harsh to start is if Debajyoti arrives after $1$ second. Note that this $1$ second will not be counted in the final answer.
• The lights will be now at $\{4,6,1,0,8,7\}$, so Harsh can drive from the $1$-st light to the $2$-nd light, which requires $0$ seconds to travel.
• The lights are still at $\{4,6,1,0,8,7\}$. Harsh must wait $3$ seconds for the $2$-nd light to turn green, before going to the $3$-rd light, which requires $0$ seconds to travel.
• The lights are now at $\{7,0,4,3,2,1\}$, so Harsh continues to the $4$-th light, which requires $0$ seconds to travel.
• The lights are still at $\{7,0,4,3,2,1\}$, so Harsh continues to the $5$-th light, which requires $0$ seconds to travel.
• The lights are still at $\{7,0,4,3,2,1\}$, so Harsh continues to the $6$-th light, which requires $0$ seconds to travel.
• The lights are still at $\{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=3$ seconds.