Canadian Computing Olympiad: 2021 Day 2, Problem 3

Some cities have complicated road networks that require advanced graph theory to analyze. But not Loop Town! Loop Town has a single circular road that loops around the town. It has $N$ residents that live in $N$ distinct houses located around the road. The town also has $N$ offices, and each resident works at a distinct office.

The road in Loop Town has length $L$. The location of each building will be represented by an integer between $0$ and $L-1$. Since the road is circular, the positions $0$ and $L-1$ are adjacent. It is guaranteed that the locations of all $2N$ buildings will be distinct.

Every morning, all $N$ residents simultaneously exit their houses onto the road. They then need to walk along the road to the entrance of the office where they work. When each resident has reached the entrance of their office, they all enter simultaneously.

However, a pandemic has now come to Loop Town, disrupting this usual routine. To prevent the spread of disease, residents must now observe social distancing while walking to work. Since the loop road is rather narrow, this means that it is far more inconvenient for two people to cross each other on their way to work (one person must temporarily step off the path to let the other pass). What is the minimum total number of crossings, assuming all the residents work together to achieve this?

Input Specification

The first line contains the two integers $N$ and $L$ $(1\le N\le 1000000,1\le L\le {10}^9)$.

The $i$-th of the next $N$ lines contains the two integers $a_i$ and $b_i$ $(0\le a_i,b_i<L)$, where $a_i$ and $b_i$ represent the locations of the $i$-th resident's house and office respectively. It is guaranteed that all $2N$ locations are distinct.

For 12 of the 25 available marks, $N\le 5000$.

For an additional 6 of the 25 available marks, $N\le 100000$.

Output Specification

On a single line, output the minimum total number of crossings.

Sample Input 1

3 100
10 50
30 20
60 40

Sample Output 1

0

Explanation for Sample Output 1

Since the road is circular, nobody needs to cross each other.

Sample Input 2

4 100
30 70
10 12
60 75
90 50

Sample Output 2

1