AT_abc467_e [ABC467E] Adjacent Sums (hard)

**※ E 問題の問題文は C 問題と同じです。赤字で示された制約のみが異なります。** $ 0 $ 以上 $ M-1 $ 以下の整数からなる整数列 $ A=(A_1,A_2,\dots,A_N),B=(B_1,B_2,\dots,B_{N-1}) $ が与えられます。 $ A,B $ の長さはそれぞれ $ N,N-1 $ です。 $ A $ に対して以下の操作を好きな回数行うことができます。 - $ 1 $ 以上 $ N $ 以下の整数 $ i $ を $ 1 $ つ選び、 $ A_i $ に $ 1 $ を加える。 以下の条件を満たすようにするために必要な操作回数の最小値を求めてください。 なお、問題の制約下では、必ず条件を満たすようにできることが証明できます。 - $ i=1,2,\dots,N-1 $ について、 $ A_i+A_{i+1} $ を $ M $ で割った余りは $ B_i $ に等しい。

入力は以下の形式で標準入力から与えられる。 > $ N $ $ M $ $ A_1 $ $ A_2 $ $ \ldots $ $ A_N $ $ B_1 $ $ B_2 $ $ \ldots $ $ B_{N-1} $

答えを $ 1 $ 行で出力せよ。

### Sample Explanation 1 $ 1 $ 回目の操作で $ i=2 $ を選ぶと、 $ A=(4,7,7) $ となります。 $ 2 $ 回目の操作で $ i=1 $ を選ぶと、 $ A=(5,7,7) $ となります。 $ 3 $ 回目の操作で $ i=1 $ を選ぶと、 $ A=(6,7,7) $ となります。 $ 4 $ 回目の操作で $ i=2 $ を選ぶと、 $ A=(6,8,7) $ となります。 $ 5 $ 回目の操作で $ i=1 $ を選ぶと、 $ A=(7,8,7) $ となります。 $ A_1+A_2=7+8=15,\;A_2+A_3=8+7=15 $ なので、条件を満たします。 また、 $ 4 $ 回以下の操作で条件を満たすようにはできないため、答えは $ 5 $ です。 ### Constraints - $ 2 \leq N \leq 2 \times 10^5 $ - $ 3 \leq M \leq 10^9 $ - $ 0 \leq A_i \leq M-1 $ - $ 0 \leq B_i \leq M-1 $ - 入力される値はすべて整数