题目描述

我们称任意相邻的 $2$ 个元素都不相同的整数序列为好序列。

给定长度为 $N$ 的好序列 $A=(A_1,A_2,\dots,A_N)$ 和 $B=(B_1,B_2,\dots,B_N)$。其中，$A,B$ 的每个元素都在 $0$ 以上且小于 $M$。

你可以对 $A$ 进行任意次（包括 $0$ 次）如下操作：

• 选择 $1$ 到 $N$ 之间的一个整数 $i$，并执行以下两种操作之一：
  • 令 $A_i\leftarrow (A_i+1)\bmod M$。
  • 令 $A_i\leftarrow (A_i-1)\bmod M$。其中，$(-1)\bmod M=M-1$。

但不能进行使 $A$ 变成不是好序列的操作。

请判断是否可以将 $A$ 变为 $B$，如果可以，求出将 $A$ 变为 $B$ 所需的最小操作次数。

输入格式

输入通过标准输入按以下格式给出。

$N$ $M$ $A_1$ $A_2$ $\dots$ $A_N$ $B_1$ $B_2$ $\dots$ $B_N$

输出格式

如果不可能，将 -1 输出。

如果可能，请输出最小操作次数的整数。

样例 1

输入

3 9
2 0 1
4 8 1

输出

3

样例 2

输入

3 9
1 8 2
1 8 2

输出

0

样例 3

输入

24 182
128 115 133 52 166 92 164 119 143 99 54 162 86 2 59 166 24 78 81 5 109 67 172 99
136 103 136 28 16 52 2 85 134 64 123 74 64 28 85 161 19 74 14 110 125 104 180 75

输出

811

说明/提示

限制条件

• $2\leq N\leq 2\times 10^5$
• $2\leq M\leq 10^6$
• $0\leq A_i,B_i < M\ (1\leq i\leq N)$
• $A_i\ne A_{i+1}\ (1\leq i\leq N-1)$
• $B_i\ne B_{i+1}\ (1\leq i\leq N-1)$
• 输入均为整数

样例解释 1

如下操作可以在 $3$ 次内达成目标。

• 令 $A_1\leftarrow (A_1+1)\bmod M$，此时 $A=(3,0,1)$。
• 令 $A_2\leftarrow (A_2-1)\bmod M$，此时 $A=(3,8,1)$。
• 令 $A_1\leftarrow (A_1+1)\bmod M$，此时 $A=(4,8,1)$。

无法在 $2$ 次及以下操作内达成目标，因此答案为 $3$。

例如，第一次操作如果令 $A_2\leftarrow (A_2+1)\bmod M$，则 $A=(2,1,1)$，此时 $A$ 不是好序列，因此该操作不允许。

样例解释 2

一开始 $A$ 和 $B$ 就相等的情况也是可能的。

由 ChatGPT 4.1 翻译