Problem Description

A sequence of integers where every two adjacent elements are different is called a good sequence.

You are given two good sequences of length $N$, $A=(A_1,A_2,\dots,A_N)$ and $B=(B_1,B_2,\dots,B_N)$. Each element of $A$ and $B$ is between $0$ and $M-1$ inclusive.

You can perform the following operation on $A$ any number of times (including zero):

• Choose an integer $i$ between $1$ and $N$ inclusive, and perform one of the following operations:
• Set $A_i$ to $(A_i+1) \mod M$.
• Set $A_i$ to $(A_i-1) \mod M$, where $(-1) \mod M = M-1$.

However, you cannot perform an operation that would make $A$ not a good sequence.

Determine if it is possible to make $A$ equal to $B$, and if so, find the minimum number of operations required to do so.

Input Format

The input is given from the standard input in the following format:

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

Output Format

If it is not possible, output -1.

If it is possible, output the minimum number of operations as an integer.

Sample Input and Output

Sample Input #1

3 9
2 0 1
4 8 1

Sample Output #1

3

Sample Input #2

3 9
1 8 2
1 8 2

Sample Output #2

0

Sample Input #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

Sample Output #3

811

Notes/Hints

Constraints

• $2 \leq N \leq 2 \times 10^5$
• $2 \leq M \leq 10^6$
• $0 \leq A_i, B_i < M$ (for $1 \leq i \leq N$)
• $A_i \ne A_{i+1}$ (for $1 \leq i \leq N-1$)
• $B_i \ne B_{i+1}$ (for $1 \leq i \leq N-1$)
• All inputs are integers

Sample Explanation 1

You can achieve the goal in 3 operations as follows:
- Set $A_1$ to $(A_1+1) \mod M$. $A$ becomes $(3,0,1)$.
- Set $A_2$ to $(A_2-1) \mod M$. $A$ becomes $(3,8,1)$.
- Set $A_1$ to $(A_1+1) \mod M$. $A$ becomes $(4,8,1)$.
It is not possible to achieve the goal in 2 or fewer operations, so the answer is 3. For example, performing the first operation by setting $A_2$ to $(A_2+1) \mod M$ is not allowed because it would make $A$ not a good sequence, resulting in $(2,1,1)$.

Sample Explanation 2

It is possible that $A$ and $B$ are already equal from the beginning.

见题面 Input 部分

见题面 Output 部分