My roommate has recently taken a liking to a cute girl. With her birthday coming up, he decided to buy a pair of couple bracelets, one for himself and one for her. Each bracelet has $n$ ornaments, and each ornament has a certain brightness.

However, the day before her birthday, my roommate suddenly realized he might have picked up the wrong bracelet, and there is no time left to exchange it! He can only use a special method: increase the brightness of all ornaments on one of the bracelets by the same natural number $c$ (a non-negative integer). Furthermore, since the bracelet is circular, it can be rotated by any angle, but because the orientation of the ornaments is fixed, the bracelet cannot be flipped. After adjusting the brightness and rotating the bracelet, he wants to minimize the difference between the two bracelets.

After rotating the two bracelets and aligning the ornaments, we label the ornaments counter-clockwise starting from a certain position as $1, 2, \dots, n$, where $n$ is the number of ornaments on each bracelet. Let $x_i$ be the brightness of the ornament at position $i$ on the first bracelet, and $y_i$ be the brightness of the ornament at position $i$ on the second bracelet. The difference between the two bracelets is defined as:

$$\sum_{i=1}^{n} (x_i - y_i)^2$$

Please help him calculate the minimum possible difference after performing the adjustments (brightness modification and rotation).

Input

The first line of the input contains two integers $n$ and $m$, where $n$ is the number of ornaments on each bracelet, and the initial brightness of each ornament is at most $m$.

The next two lines each contain $n$ integers, representing the brightness of the ornaments on the first and second bracelets, respectively, starting from a certain position and moving counter-clockwise.

Output

Output a single integer representing the minimum difference between the two bracelets. Note that after modifying the brightness, the brightness of the ornaments can exceed $m$.

Examples

Input 1

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

Output 1

1

Note

For the example, we need to increase the brightness of the first bracelet by $1$, making the brightness of the first bracelet: $2, 3, 4, 5, 6$. Rotate the second bracelet. For this example, it means cyclically shifting the brightness of the second bracelet $6, 3, 3, 4, 5$ to the left by one position, making the final brightness of the second bracelet: $3, 3, 4, 5, 6$. At this point, the difference between the two bracelets is $1$.

Constraints

• $30\%$ of the data satisfies $n \le 500, m \le 10$;
• $70\%$ of the data satisfies $n \le 5000$;
• $100\%$ of the data satisfies $1 \le n \le 50000, 1 \le m \le 100, 1 \le a_i \le m$.