配点 : $700$ 点

問題文

$L$ 個のマスが横一列に並んでいます． マスは左から順に $1,2,\ldots,L$ と番号が振られています．

$N$ 匹のペンギンがマス目の上にいます． ペンギンは左から順に $1,2,\ldots,N$ と番号が振られています． 最初，ペンギン $i$ はマス $A_i$ の上にいます． ここで，$1 \leq A_1 < A_2 < \ldots < A_N \leq L$ です．

あなたは，次の操作を好きな回数行うことができます．

• ペンギンを $1$ 匹選び，左または右へ向かって滑らせる． ペンギンは，目の前に空マスがある限り滑り続ける． 別のペンギンのいるマスの直前のマスに到達する，もしくは目の前にマスが存在しなくなったら，ペンギンは停止する．

例えば，$N=3,L=10$ で，ペンギンのいるマスが $(2,3,7)$ であるとします． このとき，ペンギン $2$ を右に滑らせると，ペンギン $2$ はマス $6$ まで移動します． また，ペンギン $3$ を右に滑らせると，ペンギン $3$ はマス $10$ まで移動します．

あなたの目標は，すべての $i$ について，ペンギン $i$ がマス $B_i$ の上にいるようにすることです． ここで，$1 \leq B_1 < B_2 < \ldots < B_N \leq L$ です． 目標が達成可能か判定し，可能ならば必要な操作回数の最小値を求めてください．

制約

• $1 \leq N \leq 10^5$
• $N \leq L \leq 10^9$
• $1 \leq A_1 < A_2 < \ldots < A_N \leq L$
• $1 \leq B_1 < B_2 < \ldots < B_N \leq L$
• 入力される数はすべて整数．

入力

入力は以下の形式で標準入力から与えられる．

$N$ $L$

$A_1$ $A_2$ $\cdots$ $A_N$

$B_1$ $B_2$ $\cdots$ $B_N$

出力

目標が達成不可能な場合は $-1$ を，可能な場合は必要な操作回数の最小値を出力せよ．

4 11
3 4 6 10
1 5 6 11

3

次のように操作すればよいです．

• ペンギン $1$ を左に滑らせる．ペンギンの位置は，$(1,4,6,10)$ になる．
• ペンギン $2$ を右に滑らせる．ペンギンの位置は，$(1,5,6,10)$ になる．
• ペンギン $4$ を右に滑らせる．ペンギンの位置は，$(1,5,6,11)$ になる．

1 3
1
2

-1

10 1000000000
65110170 68805223 123016442 275946481 661490312 760727752 764540566 929355340 930658577 947099792
1 2 123016442 661490311 929355337 930658574 999999997 999999998 999999999 1000000000

13