Minimizing Road Crossings in a Circular Town

In a circular town there are \(n\) citizens, \(n\) houses and \(n\) offices. Each citizen lives in a unique house and works in a unique office. All \(2n\) buildings are located at distinct integer positions on the circle, with positions in \([0, l-1]\) and the circumference of the circle is \(l\). Every morning each citizen leaves his house at the same time and walks along the circle in one of the two possible directions (clockwise or anticlockwise) to his office. However, due to a pandemic the leadership requires maintaining social distancing. When two citizens’ walking paths on the narrow circular road overlap (i.e. they share a common segment on the road) it causes inconvenience, and such crossings should be minimized. (Note that three or more citizens meeting at a point is forbidden.)

For citizen \(i\), let \(H_i\) and \(O_i\) be the positions of his house and office respectively. The clockwise distance from \(H_i\) to \(O_i\) is defined as \(d_i = (O_i - H_i + l) \bmod l\), and the anticlockwise distance is \(l - d_i\). Thus, citizen \(i\) may choose one of two arcs:

• If he chooses the clockwise direction and \(d_i \leq \frac{l}{2}\), his path will cover an arc of length \(d_i\), represented (after normalization) as an interval \([H_i, O_i]\) if \(H_i \le O_i\) or \([H_i, O_i+l]\) if \(H_i>O_i\).
• If he chooses the anticlockwise direction (when \(d_i > \frac{l}{2}\)) his path will cover an arc of length \(l-d_i\). In this case, after normalization the interval is \([O_i, H_i]\) if \(O_i \le H_i\) or \([O_i, H_i+l]\) if \(O_i>H_i\).
• Ambiguous Case: When \(d_i = \frac{l}{2}\) the two arcs are of equal length. In such cases, for simplicity, choose the interval \([\min(H_i,O_i), \max(H_i,O_i)]\).

The leadership can decide for each citizen which direction he should take, with the goal of minimizing the total number of pairwise route crossings (i.e. the number of pairs of citizens whose chosen intervals overlap in their interiors). Two intervals \([s_1,e_1]\) and \([s_2,e_2]\) (with \(s_1 < e_1\) and \(s_2 < e_2\)) are considered to overlap (thus contributing one to the crossing count) if
\[ \max(s_1,s_2) < \min(e_1,e_2). \]

Given \(n\), \(l\), the positions of the \(n\) houses and the \(n\) offices (where the \(i\)th house and the \(i\)th office belong to the \(i\)th citizen), determine the minimum total number of pairwise overlapping (crossing) routes possible by assigning the walking direction for each citizen optimally.

inputFormat

The input consists of three lines:

1. The first line contains two integers \(n\) and \(l\) (the number of citizens and the circumference of the circle).
2. The second line contains \(n\) space‐separated integers representing the positions of the houses.
3. The third line contains \(n\) space‐separated integers representing the positions of the offices.

outputFormat

Output a single integer: the minimum total number of pairwise route crossings.

sample

2 10
1 8
3 9

0