Minimizing Table Rotations for Uyghur Polo Assignment

Wowo is a hospitable Xinjiang uncle who will serve k guests traditional Uyghur Polo around a big round table with n uniformly placed chairs (n ≥ k). Each guest sits at one of the chairs (all different) and k bowls of Uyghur Polo are initially placed on the table, each beside a chair (possibly an empty one), with no two bowls at the same position.

The table can be rotated. In one rotation you may turn the table by an angle of \(\frac{2\pi}{n}\) either clockwise or counterclockwise. When the table is rotated, the bowls (which are on the table) move together with it, while the chairs and guests remain fixed. When a bowl is in front of a guest, the guest may take it (or wait for another bowl in a subsequent rotation).

Your task is to assign each guest exactly one bowl by a sequence of rotations. Since rotating the table takes time, you want to minimize the total number of rotation moves. Formally, the table is a circle. The chairs occupy the points \(0, 1, \ldots, n-1\) in counterclockwise order, with the convex hull forming a regular polygon. The \(i\)-th bowl is initially at point \(b_i\) (\(0 \le b_i < n\)) and the \(i\)-th guest is at point \(a_i\) (\(0 \le a_i < n\)). A counterclockwise rotation increases a bowl's position by one modulo \(n\) (i.e. the bowl at \(b_i\) moves to \(b_i+1 \bmod n\)), and a clockwise rotation decreases a bowl's position by one modulo \(n\).

One can view the problem as follows. For a guest at position \(a\) who is to receive a bowl originally at position \(b\), the table must be rotated a number of times \(r\) so that

[ r \equiv a - b \pmod{n}. ]

You are allowed to perform rotations one step at a time (each step costs 1 move) and you may serve several guests in one rotation if the corresponding bowl comes in front of the guest. Devise an optimal assignment of bowls to guests (by possibly reordering the bowls using rotations) and a sequence of rotations so that each guest gets one bowl and the total number of rotations is minimized.

inputFormat

The first line contains two integers (n) and (k) ((n \ge k)). The second line contains (k) space-separated integers representing the positions of the guests (a_i) ((0 \le a_i < n)). The third line contains (k) space-separated integers representing the positions of the bowls (b_i) ((0 \le b_i < n)).

outputFormat

Output a single integer: the minimum total number of rotations required for all guests to receive a bowl.

sample

10 3
1 3 9
2 5 7

4