管理者より

問題文

あるオンライン会議に、$N$人の社員が家から参加しています。
社員にはそれぞれ社員番号$1,2,...,N$が割り振られています。
社員$i$の家のインターネット回線は、送信（上り）に$A_i$秒、受信（下り）に$B_i$秒かかります。

このオンライン会議で、社員$1$から点呼をとります。
社員$j$ ($2\le j\le N$)は、以下の条件の一つが満たされた瞬間に「$j$」と叫びます。
・$j-1$の数字が聞こえた
・$j-2$の数字が聞こえてから$K$秒経っても、$j-1$の数字が聞こえない
ただし、j=2の場合は、一つ目の条件が満たされたときに叫びます。

社員$1$が「$1$」と叫んでから、社員全員が自分の番号を叫ぶまで何秒かかるでしょうか。

入力

$NK$
$A_1$ $A_2$ $\cdots$ $A_N$
$B_1$ $B_2$ $\cdots$ $B_N$

・入力は全て整数
・$1\le N\le {10}^5$
・$0\le K\le {10}^8$
・$0\le A_i,B_i\le {10}^8$

出力

社員$1$が「$1$」と叫んでから、社員全員が自分の番号を叫ぶまでにかかる秒数を出力してください。
最後に改行してください。

サンプル

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