Dankey Kang still obeys traffic laws, like any good ape.

Fax McClad, Croneria's most diligent bounty hunter, is waiting for Dankey Kang to exit his hideout so he can capture him. In order to avoid capture, Dankey Kang asks for your assistance.

Dankey Kang needs to travel from his initial hideout to another hideout to deliver goods (they're green). A straight road with ~N~ traffic lights connects the two hideouts, numbered in order from ~1~ to ~N~. Each traffic light has a cycle length of ~T~ seconds. The ~i^\text{th}~ traffic light is green (meaning that Dankey Kang can go, but he may choose not to, angering the other drivers on the road) for ~g_i~ seconds, and red (meaning that Dankey Kang must stop) for the remaining ~T-g_i~ seconds. Each light's cycle repeats indefinitely and initially, the light is ~o_i~ seconds into its cycle (a light with ~o_i = 0~ has just turned green). In the case that Dankey Kang arrives at a light at the same time it changes color, he will obey the new color.

Also, for the ~i^\text{th}~ traffic light from light ~1~ to light ~N-1~, ~t_i~ seconds are required to travel to the next traffic light. Dankey Kang's initial hideout is located just before the first light and he reaches the other hideout as soon as he passes the ~N^\text{th}~ light. In other words, no time is required to reach the first light from the initial hideout or to reach the other hideout from the ~N^\text{th}~ light.

Dankey Kang wants to minimize the amount of time he spends exposed on the road. Anytime he spends waiting in the initial hideout is not counted, but he must wait in his hideout for a non-negative integer number of seconds. Can you tell him the minimum amount of time necessary to reach the destination?

Constraints

In all subtasks:

~1 \le N~

~2 \le T~

~1 \le g_i < T~

~0 \le o_i < T~

~0 \le t_i \le 10^9~

Subtask	Points	~N~	~T~
1	20	~N \le 1\,000~	~T \le 1\,000~
2	20	~N \le 1\,000~	~T \le 10^9~
3	60	~N \le 200\,000~	~T \le 10^9~

Input Specification

The first line of input will contain two space-separated integers, ~N~ and ~T~.

~N~ lines of input follow. The ~i^\text{th}~ line will contain 2 space separated integers, ~g_i~ and ~o_i~.

~N-1~ lines of input follow. The ~i^\text{th}~ line will contain ~t_i~.

Output Specification

On a single line, output the minimum amount of time Dankey Kang must spend on the road.

Sample Input

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

Sample Output

11

Explanation for Sample Output

Initially, the ~5~ traffic lights are at the following seconds in their cycle: ~\{2,3,6,2,0\}~.

An optimal strategy for Dankey Kang begins with waiting for ~1~ second. Note that this ~1~ second will not be counted in the final answer.

The lights are now at ~\{3,4,7,3,1\}~, so Dankey Kang can travel from the first light to the second light, which requires ~1~ second to travel.

The lights are now at ~\{4,5,8,4,2\}~, so Dankey Kang can continue traveling, without stopping, to the third light, which requires ~2~ seconds to travel.

The lights are now at ~\{6,7,0,6,4\}~, so Dankey Kang can continue traveling, without stopping, to the fourth light, which requires ~3~ seconds to travel.

The lights are now at ~\{9,0,3,9,7\}~. Dankey Kang must wait ~1~ second for the ~4^\text{th}~ light to turn green before going to the fifth light, which requires ~4~ seconds to travel.

The lights are now at ~\{4,5,8,4,2\}~, so Dankey Kang can continue traveling, without stopping, to the destination hideout. The total time that Dankey Kang takes for this route is ~1+2+3+1+4 = 11~.