Problem Description

Loop Town has $n$ citizens, $n$ houses, and $n$ offices. Each citizen lives in one house and works in one office. No two citizens live in the same house, and no two citizens work in the same office.

Loop Town is a circular city, and traveling one full lap around the city has length $l$. All $2n$ buildings (houses and offices) are located at integer points on the circle. Their positions can be described by integers in the range $[0, l - 1]$, and all $2n$ building positions are distinct.

Every morning, each citizen starts from their house at the same time and walks along the circular road to their office. After reaching the office, they do not enter immediately. Instead, they wait until all citizens have arrived at their offices, and then everyone enters and starts working at the same time.

A pandemic has broken the usual routine, and the leader requires each citizen to keep social distance. The circular road around the city is narrow. If two citizens’ routes intersect, it is very inconvenient (one person must temporarily leave the road to let the other pass), and it is forbidden for three or more people to be at the same place at the same time.

The leader can assign each citizen a commuting route, i.e., which direction along the circular road they walk. The leader’s goal is to minimize the total number of intersections between the routes of any two citizens. Find this minimum value.

Input Format

The first line contains two integers $n, l$.

The next $n$ lines each contain two integers $a_i, b_i$, representing the positions of the $i$-th citizen’s house and office.

Output Format

One line containing one integer, representing the required value.

3 100
10 50
30 20
60 40

0

4 100
30 70
10 12
60 75
90 50

1

Hint

Constraints

For $\frac{4}{13}$ of the testdata, $1 \leq n \leq 5 \times 10^3$.

For $\frac{8}{13}$ of the testdata, $1 \leq n \leq 10^5$.

For $100\%$ of the testdata, $1 \leq n \leq 10^6$, $1 \leq l \leq 10^9$, $0 \leq a_i, b_i < l$, and it is guaranteed that $a_i, b_i$ are all distinct.

Source

CCO2021 D2T3

Translated by ChatGPT 5