题目描述

译自 NOISG 2021 Final T3. Password

神秘的怪盗卢平四世（通常简称为卢平）接受了一项艰巨任务：闯入世界上最大、最壮观、技术最先进的加利亚斯特罗城堡的保险库。城堡配备了最先进的科技，拥有顶级的安保系统，充分利用了人力与机器的能力。然而，面对如此挑战，卢平毫不畏惧。他巧妙地避开了城堡周围的卫兵和监控摄像头，突破了众多陷阱，解决了许多谜题，终于到达了保险库。在那里，他黑进了监控系统，显示出毫无破绽的画面，并用药物使所有卫兵失去意识。

他面临的最后障碍是一个电子密码系统，输入正确密码后即可打开保险库。初始时，屏幕上显示 $N$ 个 $0$ 到 $K$ 之间的非负整数，第 $i$ 个为 $A_i$。密码也由 $N$ 个 $0$ 到 $K$ 之间的非负整数组成。通过他卓越的智慧和敏捷的身手，卢平确定密码的第 $i$ 个数字为 $P_i$ $(1 \leq i \leq N)$。得知密码后，卢平欣喜若狂，准备完成任务。然而，令他沮丧的是，输入密码的方式非常奇特且耗时，涉及缓慢但稳定地更改屏幕上数字的操作。

假设当前屏幕上第 $i$ 个数字为 $C_i$ $(1 \leq i \leq N)$。当对于所有 $1 \leq i \leq N$，$C_i = P_i$ 时，卢平可以打开保险库。否则，卢平可以执行以下操作：选择两个整数 $i, j$，满足 $1 \leq i \leq j \leq N$，对于所有 $i \leq l \leq j$ 的整数 $l$，将 $C_l$ 更改为 $C_l + 1 \pmod{K+1}$。换句话说，将 $C_l + 1$ 除以 $K+1$ 后的余数作为新的 $C_l$。具体来说，$0$ 变为 $1$，$1$ 变为 $2$，……，$K-1$ 变为 $K$，$K$ 变为 $0$。

更糟糕的是，卢平还得知他的宿敌泽尼加达警探正赶来抓住他。为了尽快打开保险库并逃脱，卢平希望使用最少次数的操作将初始数字更改为密码，打开保险库。你的任务是确定卢平所需的最少操作次数。

输入格式

程序需从标准输入读取数据。

第一行包含两个整数 $N$ 和 $K$。

第二行包含 $N$ 个整数 $A_1, A_2, \ldots, A_N$，其中 $A_i$ 是屏幕上初始显示的第 $i$ 个数字。

第三行包含 $N$ 个整数 $P_1, P_2, \ldots, P_N$，其中 $P_i$ 是密码的第 $i$ 个数字。

输出格式

程序需向标准输出输出结果。
输出一行，包含一个整数，表示卢平将屏幕上的数字更改为密码所需的最少操作次数。

3 4
1 2 0
2 1 2

4

最优操作序列是选择 $(i, j) = (1, 3)$ 一次，$(2, 3)$ 一次，$(2, 2)$ 两次。

这个样例满足子任务 $1, 4, 5, 6, 7$ 的限制。

7 1
1 0 1 0 1 1 1
0 0 1 1 0 1 0

3

最优操作序列是选择 $(i, j) = (1, 3)$ 一次，$(2, 6)$ 一次，$(6, 7)$ 一次。

这个样例满足子任务 $3, 4, 5, 6, 7$ 的限制。

7 9
1 5 3 4 8 3 2
7 4 8 3 2 3 1

18

这个样例满足子任务 $4, 5, 6, 7$ 的限制。

数据范围与提示

对于所有输入数据，满足：

• $1 \leq N \leq 3 \times 10^5$
• $0 \leq K \leq 10^9$
• 对于所有 $1 \leq i \leq N$，$0 \leq A_i, P_i \leq K$

详细子任务附加限制及分值如下表所示：