相邻和（困难版）(Adjacent Sums (hard))

题目描述

（与 C 题题面相同，仅约束中 M 的范围不同。）

给定由 0 以上 M−1 以下的整数构成的整数列 A=(A₁,A₂,…,A_N)、B=(B₁,B₂,…,B_{N−1})。A、B 的长度分别为 N、N−1。

可以对 A 进行任意次以下操作：

• 选择一个满足 1≤i≤N 的整数 i，将 A_i 加 1。

求使以下条件成立所需的最小操作次数（可以证明在本题约束下条件一定能满足）：

• 对 i=1,2,…,N−1，A_i+A_{i+1} 除以 M 的余数等于 B_i。

本题约束下 M 为 3 到 10⁹ 的整数。

输入格式

N M
A1 A2 … AN
B1 B2 … BN−1

输出格式

一行输出答案。

样例输入 #1

3 10
4 6 7
5 5

样例输出 #1

5

样例输入 #2

2 3
1 2
2

样例输出 #2

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

数据范围

• 2 ≤ N ≤ 2×10⁵
• 3 ≤ M ≤ 10⁹
• 0 ≤ A_i ≤ M−1
• 0 ≤ B_i ≤ M−1
• 输入值均为整数

知识点与难度

本题涉及的知识点从属于 GESP 5级，难度等级：⭐⭐⭐。

测试点分布