AT_abc467_e.Adjacent Sums (hard)

The problem statement of Problem E is the same as Problem C. Only the constraint shown in red differ.

You are given integer sequences $A=(A_1,A_2,\dots,A_N)$ and $B=(B_1,B_2,\dots,B_{N-1})$ consisting of integers between $0$ and $M-1$, inclusive. The lengths of $A$ and $B$ are $N$ and $N-1$, respectively.
You can perform the following operation on $A$ any number of times.

• Choose an integer $i$ with $1 \leq i \leq N$, and add $1$ to $A_i$.

Find the minimum number of operations required to satisfy the following condition.
It can be proved that the condition can always be satisfied under the constraints of this problem.

• For $i=1,2,\dots,N-1$, the remainder when $A_i+A_{i+1}$ is divided by $M$ equals $B_i$.

问题 E 的题面与问题 C 相同，仅红色标出的约束条件不同。

给定两个整数序列 $A=(A_1,A_2,\dots,A_N)$ 和 $B=(B_1,B_2,\dots,B_{N-1})$，其中每个元素均为 $0$ 到 $M-1$（含端点）之间的整数。序列 $A$ 和 $B$ 的长度分别为 $N$ 和 $N-1$。
你可以对 $A$ 执行以下操作任意多次：

• 选择一个整数 $i$，满足 $1 \leq i \leq N$，并将 $A_i$ 增加 $1$。

求满足以下条件所需的最少操作次数。
在本题约束下，可以证明该条件总能被满足。

• 对于 $i=1,2,\dots,N-1$，$(A_i+A_{i+1}) \bmod M = B_i$。

The input is given from Standard Input in the following format:

$N$ $M$
$A_1$ $A_2$ $\ldots$ $A_N$
$B_1$ $B_2$ $\ldots$ $B_{N-1}$

输入从标准输入中按以下格式给出：

$N$ $M$
$A_1$ $A_2$ $\ldots$ $A_N$
$B_1$ $B_2$ $\ldots$ $B_{N-1}$

Output the answer on one line.

在一行中输出答案。

Sample 1 Explanation:
If we choose $i=2$ for the first operation, we get $A=(4,7,7)$.
If we choose $i=1$ for the second operation, we get $A=(5,7,7)$.
If we choose $i=1$ for the third operation, we get $A=(6,7,7)$.
If we choose $i=2$ for the fourth operation, we get $A=(6,8,7)$.
If we choose $i=1$ for the fifth operation, we get $A=(7,8,7)$.
Since $A_1+A_2=7+8=15$ and $A_2+A_3=8+7=15$, the condition is satisfied.
The condition cannot be satisfied with four or fewer operations, so the answer is $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$
• All input values are integers.

样例 1 解释：
若第一次操作选择 $i=2$，则得到 $A=(4,7,7)$。
若第二次操作选择 $i=1$，则得到 $A=(5,7,7)$。
若第三次操作选择 $i=1$，则得到 $A=(6,7,7)$。
若第四次操作选择 $i=2$，则得到 $A=(6,8,7)$。
若第五次操作选择 $i=1$，则得到 $A=(7,8,7)$。
由于 $A_1+A_2=7+8=15$ 且 $A_2+A_3=8+7=15$，条件得以满足。
无法在四次或更少的操作次数内满足该条件，因此答案为 $5$。

约束条件

• $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$
• 所有输入值均为整数。