D - Increment Decrement Again Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 700 点

問題文

どの隣接する 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 に一致させるために必要な最小の操作回数を求めてください。

制約

  • 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)
  • 入力はすべて整数

入力

入力は以下の形式で標準入力から与えられる。

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

出力例 1

3

以下のようにすると、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 です。

例えば、1 回目の操作で A_2\leftarrow (A_2+1)\bmod M とすることは許されません。この操作を行うと A=(2,1,1) となり、A が良い数列でなくなってしまうためです。

入力例 2

3 9
1 8 2
1 8 2

出力例 2

0

はじめから A と B が等しい場合もあります。

入力例 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

出力例 3

811

Score : 700 points

Problem Statement

An integer sequence where no two adjacent elements are the same 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 operations on A any number of times, possibly zero:

  • Choose an integer i between 1 and N, inclusive, and perform one of the following:
    • Set A_i \leftarrow (A_i + 1) \bmod M.
    • Set A_i \leftarrow (A_i - 1) \bmod M. Here, (-1) \bmod M = M - 1.

However, you cannot perform an operation that makes A no longer a good sequence.

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

Constraints

  • 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)
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

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

Output

If the goal is unachievable, print -1.

Otherwise, print the minimum number of operations required as an integer.

Sample Input 1

3 9
2 0 1
4 8 1

Sample Output 1

3

You can achieve the goal in three operations as follows:

  • Set A_1 \leftarrow (A_1 + 1) \bmod M. Now A = (3, 0, 1).
  • Set A_2 \leftarrow (A_2 - 1) \bmod M. Now A = (3, 8, 1).
  • Set A_1 \leftarrow (A_1 + 1) \bmod M. Now A = (4, 8, 1).

It is impossible to achieve the goal in two or fewer operations, so the answer is 3.

For example, you cannot set A_2 \leftarrow (A_2 + 1) \bmod M in the first operation, because it would make A = (2, 1, 1), which is not a good sequence.

Sample Input 2

3 9
1 8 2
1 8 2

Sample Output 2

0

A and B might be equal from the beginning.

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