题目描述

本题与 C 题（Adjacent Sums (easy)）题面完全相同，只有 $M$ 的取值范围不同：本题 $M \ge 3$ 且最大可达 $10^9$。

给定两个整数序列 $A = (A_1, A_2, \ldots, A_N)$ 和 $B = (B_1, B_2, \ldots, B_{N-1})$，其中每个元素都在 $0$ 到 $M-1$ 之间。$A$ 的长度是 $N$，$B$ 的长度是 $N-1$。

你可以对 $A$ 进行任意多次下面的操作：

• 选一个整数 $i$（$1 \le i \le N$），把 $A_i$ 加 $1$。

请求出使下面条件成立所需的最少操作次数（题目保证在本题约束下一定可以做到）：

• 对每个 $i = 1, 2, \ldots, N-1$，$A_i + A_{i+1}$ 除以 $M$ 的余数等于 $B_i$。

注意：操作只能加 $1$，不能减，但可以无限次加。

输入格式

N M
A_1 A_2 ... A_N
B_1 B_2 ... B_{N-1}

输出格式

在一行中输出最少操作次数。

输入示例 1

3 10
4 6 7
5 5

输出示例 1

5

示例 1 说明

一种最优方案（共 $5$ 次操作）：

• 对 $i=2$ 加一次，$A = (4,7,7)$；
• 对 $i=1$ 加三次，$A = (7,7,7)$；
• 对 $i=2$ 再加一次，$A = (7,8,7)$。

此时 $A_1 + A_2 = 15$，$15 \bmod 10 = 5 = B_1$；$A_2 + A_3 = 15$，$15 \bmod 10 = 5 = B_2$，条件成立。

可以证明 $4$ 次以内做不到，所以答案是 $5$。

输入示例 2

2 3
1 2
2

输出示例 2

2

示例 2 说明

只有一个条件 $A_1 + A_2 \equiv 2 \pmod 3$。当前 $1 + 2 = 3 \equiv 0$，不满足。把 $A_2$ 加两次得到 $A = (1,4)$，$1+4 = 5 \equiv 2 \pmod 3$，成立，共 $2$ 次操作。

输入示例 3

10 10
0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1

输出示例 3

40

示例 3 说明

这里 $A = (0,1,2,\ldots,9)$、$B = (9,8,\ldots,1)$、$M = 10$。注意到当前每一对相邻和恰好是 $A_i + A_{i+1} = 2i - 1$，而要求的 $B_i = 10 - i$，两者相差不小，需要多次操作。

最优方案总共需要 $40$ 次操作。本组数据的意义在于：它的最优 $x_1$ 并不是 $0$，能卡住「只试 $x_1 = 0$」的错解。

约束条件

• $2 \le N \le 2 \times 10^5$
• $\bm{3 \le M \le 10^9}$
• $0 \le A_i \le M-1$
• $0 \le B_i \le M-1$
• 所有输入值均为整数