Description

My roommate recently fell for a cute girl. Her birthday is coming up, and he decided to buy a pair of couple bracelets: one for himself and one for her. Each bracelet has $n$ decorations, and each decoration has a certain brightness.

However, on the day before her birthday, my roommate suddenly realized that he might have picked up the wrong bracelet, and there is no time to replace it. He can only use a special method: increase the brightness of all decorations on one of the bracelets by the same non-negative integer $c$. Since a bracelet is a circle, it can be rotated by any angle, but because the orientation of the decorations is fixed, the bracelet cannot be flipped. After applying the brightness modification and rotation, we want to minimize the difference value between the two bracelets.

After rotating both bracelets and aligning the decorations, starting from some aligned position and numbering the decorations from $1$ to $n$ in counterclockwise order (where $n$ is the number of decorations on each bracelet), the brightness of the decoration at position $i$ on the first bracelet is $x_i$, and that on the second bracelet is $y_i$. The difference value between the two bracelets is:

Please help compute the minimal possible difference value after applying the allowed brightness modification and rotation.

Input Format

The first line contains two integers $n, m$, where each bracelet has $n$ decorations, and the initial brightness of each decoration is at most $m$.

The next two lines each contain $n$ integers, representing the brightness of the decorations on the first and second bracelets, respectively, listed in counterclockwise order starting from some position.

Output Format

Output a single integer: the minimal difference value that can be achieved between the two bracelets. Note that after the modification, the brightness of decorations may exceed $m$.

5 6
1 2 3 4 5
6 3 3 4 5

1

Hint

Sample explanation:

Increase the brightness of the first bracelet by $1$, making it $2, 3, 4, 5, 6$.

Rotate the second bracelet. In this sample, cyclically shift the second bracelet $6, 3, 3, 4, 5$ left by one position, making it $3, 3, 4, 5, 6$.

The difference value is $1$.

Constraints:

• For $30\%$ of the testdata, $n \le 500$, $m \le 10$.
• For $70\%$ of the testdata, $n \le 5000$.
• For $100\%$ of the testdata, $1 \le n \le 50000$, $1 \le x_i, y_i \le m \le 100$.

Translated by ChatGPT 5