P11301 [NOISG 2021 Finals] Password

神秘的怪盗鲁邦四世（通常称为鲁邦）接下了一项艰巨任务——闯入世界上最大、最宏伟、最先进的城堡：“卡利奥斯特罗城堡”的金库。尽管城堡有最顶尖的安保系统，鲁邦依然无所畏惧。他成功绕过了守卫和监控，破解了许多陷阱和谜题，最终抵达金库。 然而，金库的最后一道防线是一个电子密码系统。密码系统需要输入正确的密码才能打开金库。屏幕上最初显示了 $N$ 个非负整数，编号为 $A_i$。密码由 $N$ 个数字 $P_i$ 组成，且所有数字范围均为 $0$ 到 $K$。通过鲁邦的天才智慧，他推导出了密码的值。

输入密码的过程很复杂：当前显示的数字 $C_i$ 需要通过特定的操作变为密码数字 $P_i$ 才能打开金库。 操作规则如下： - 选择两个整数 $i, j$，其中 $1 \leq i \leq j \leq N$。 - 对所有满足 $i \leq l \leq j$ 的数字 $C_l$，将其更改为 $C_l + 1 \mod (K + 1)$。 鲁邦希望用最少的操作次数将屏幕上的数字转变为密码。

- 第一行包含两个整数 $N$ 和 $K$。 - 第二行包含 $N$ 个整数 $A_1, A_2, \dots, A_N$，表示初始显示的数字。 - 第三行包含 $N$ 个整数 $P_1, P_2, \dots, P_N$，表示密码。

输出一个整数，表示将屏幕上的数字变为密码所需的最小操作次数。

【样例解释】 - 对于样例 $1$，一个最优的操作序列为选择 $(i, j) = (1, 3)$ 一次，$(2, 3)$ 一次，以及 $(2, 2)$ 两次，总操作次数为 $4$。 - 对于样例 $2$，一个最优的操作序列为选择 $(i, j) = (1, 3)$ 一次，$(2, 6)$ 一次，以及 $(6, 7)$ 一次，总操作次数为 $3$。 - 对于样例 $3$，最优的操作需要 $18$ 次。 【数据范围】 - $1 \leq N \leq 3 \times 10^5$ - $0 \leq K \leq 10^9$ - $0 \leq A_i, P_i \leq K$ | 子任务编号 | 分值 | 额外限制条件 | | :--------: | :--: | :------------------------------------------: | | $1$ | $6$ | $N \leq 3$ | | $2$ | $5$ | $A_i \leq A_{i+1}$ 且 $P_i = 0$ | | $3$ | $9$ | $K \leq 1$ | | $4$ | $10$ | $N, K \leq 80$ | | $5$ | $13$ | $N \leq 400$ | | $6$ | $23$ | $N \leq 3000$ | | $7$ | $34$ | 无额外限制 |