题目描述

循环镇有 $n$ 个公民、$n$ 座房子、$n$ 个办公室。每个公民住在一座房子中，并在一个办公室工作。没有两个公民住在同一座房子，也没有两个公民在同一个办公室工作。

循环镇是一个环形城市，绕城一圈路程为 $l$。循环镇的 $2n$ 栋建筑（房子和办公室）都在环上的整点上，其位置可以用 $[0, l - 1]$ 范围内的整数来描述，且这 $2n$ 栋建筑位置是互不相同的。

每天早上，每个公民同时从自己的房子出发，沿着环路走到自己的办公室。公民到达办公室之后不会立刻进去工作，而是要等到所有公民都到达办公室之后才会同时进入办公室开始工作。

一场疫情的到来打破了常规，领导人要求每个公民保持社交距离。围绕城市的环状道路很窄，两个公民的线路存在相互交叉时会很不方便（必须一个人暂时离开道路才能使另一个人通过），而三个人或以上禁止同时走到同一个地方。

领导人可以给每个公民规定上班路线，即走城市环路的哪一边。领导人的目标是任意两个公民线路交叉的总次数最小，求这个最小值。

输入格式

第一行，两个整数 $n, l$；

接下来 $n$ 行，每行两个整数 $a_i, b_i$，表示第 $i$ 个公民的房子和办公室的位置。

输出格式

一行，一个整数，表示所求的值。

3 100
10 50
30 20
60 40

0

4 100
30 70
10 12
60 75
90 50

1

提示

数据范围

对于 $\frac{4}{13}$ 的数据，$1 \leq n \leq 5 \times 10^3$；

对于 $\frac{8}{13}$ 的数据，$1 \leq n \leq 10^5$；

对于 $100\%$ 的数据，$1 \leq n \leq 10^6$，$1 \leq l \leq 10^9$，$0 \leq a_i, b_i < l$，保证 $a_i, b_i$ 互不相同。

题目来源

CCO2021 D2T3