From the Administrator

Problem Statement

$N$ employees are attending an online meeting from home.
The employees are assigned employee numbers $1,2,...,N$.
The internet connection at employee $i$'s home takes $A_i$ seconds to send (upload) and $B_i$ seconds to receive (download).

In this online meeting, a roll call is taken starting from employee $1$.
Employee $j$ ($2 \leq j \leq N$) shouts "$j$" at the moment one of the following conditions is satisfied.
・They hear the number $j-1$.
・$K$ seconds have passed since they heard the number $j-2$, and they still have not heard the number $j-1$.
However, in the case of j=2, the employee shouts when the first condition is satisfied.

How many seconds does it take, from when employee $1$ shouts "$1$", until all employees have shouted their own numbers?

Input

$N\ K$
$A_1$ $A_2$ $\cdots$ $A_N$
$B_1$ $B_2$ $\cdots$ $B_N$

・All inputs are integers.
・$1 \leq N \leq 10^5$
・$0 \leq K \leq 10^8$
・$0 \leq A_i, B_i \leq 10^8$

Output

Output the number of seconds it takes, from when employee $1$ shouts "$1$", until all employees have shouted their own numbers.
Print a newline at the end.

Sample

5 3
3 2 4 5 1
7 1 3 4 2

18

8 2
1 3 2 0 1 2 1 4
1 0 3 1 3 2 0 1

15

1 3
10000
10000

0