A7348. 覆盖圆环（ring）
编程题
省选/NOI-
知识点
题目描述
有一个周长为 $m$ 的圆，我们从某个点位置为起始位置，从起始位置顺时针沿着圆上移动到达的位置的点的坐标等于其移动的距离。例如下图就是一个周长为 $8$ 的圆以及部分点的坐标。
有 $n$ 组路径，给出路径的两个端点，可以在两种路径中选择其中一个。比如下图坐标点 $1$ 和坐标点 $3$ 作为路径端点，就有两种路径可以选择。
求这 $n$ 组端点的所有选择中，覆盖的圆环长度的最小值。
有 $n$ 组路径，给出路径的两个端点，可以在两种路径中选择其中一个。比如下图坐标点 $1$ 和坐标点 $3$ 作为路径端点，就有两种路径可以选择。
求这 $n$ 组端点的所有选择中，覆盖的圆环长度的最小值。
输入格式
输入的第一行包含两个整数 $n,m$，分别表示点对的数量和圆的周长。
接下来输入包含 $n$ 行，每行两个整数 $a_i,b_i$，表示路径两个端点的坐标。
接下来输入包含 $n$ 行，每行两个整数 $a_i,b_i$，表示路径两个端点的坐标。
输出格式
输出仅一个数字，即最小覆盖的长度。
输入输出样例
输入 #1
3 8 1 7 0 2 3 4
输出 #1
4
说明/提示
### 样例 1 解释
当点对选择的路径为 $7$ 顺时针到 $1$，$0$ 顺时针到 $2$，$3$ 顺时针到 $4$ 的路径所覆盖周长的长度最小，为 $4$。如下图。
### 附件
更多样例请查看：[ring test.zip](https://pms-wscdn.xmwol.com/file/0370e820c138c32f.zip)
### 数据范围
对于所有测试数据保证：
$$ 1 \le n \le 10^5 $$
$$ 1 \le m \le 10^9 $$
$$ 0 \le a_i \le b_i < m $$
| 测试点 | $n \le$ | $m \le$ | 特殊性质 |
| ----- | ------- | ------- | ----------- |
| 1 | 10 | 10 | 无 |
| 2 | 10 | 100 | 无 |
| 3~4 | 30 | 30 | 无 |
| 5~6 | $10^3$ | $10^3$ | 无 |
| 7 | $10^3$ | $10^3$ | $a_i=b_i$ |
| 8~9 | $10^3$ | $10^9$ | 无 |
| 10 | 30 | $10^4$ | 无 |
| 11~12 | $10^4$ | $10^4$ | 无 |
| 13 | $10^4$ | $10^4$ | $a_i=b_i-1$ |
| 14~15 | $10^4$ | $10^9$ | 无 |
| 16 | $10^5$ | $10^5$ | $a_i=b_i-1$ |
| 17 | $10^5$ | $10^5$ | 无 |
| 18~20 | $10^5$ | $10^9$ | 无 |
当点对选择的路径为 $7$ 顺时针到 $1$，$0$ 顺时针到 $2$，$3$ 顺时针到 $4$ 的路径所覆盖周长的长度最小，为 $4$。如下图。
### 附件
更多样例请查看：[ring test.zip](https://pms-wscdn.xmwol.com/file/0370e820c138c32f.zip)
### 数据范围
对于所有测试数据保证：
$$ 1 \le n \le 10^5 $$
$$ 1 \le m \le 10^9 $$
$$ 0 \le a_i \le b_i < m $$
| 测试点 | $n \le$ | $m \le$ | 特殊性质 |
| ----- | ------- | ------- | ----------- |
| 1 | 10 | 10 | 无 |
| 2 | 10 | 100 | 无 |
| 3~4 | 30 | 30 | 无 |
| 5~6 | $10^3$ | $10^3$ | 无 |
| 7 | $10^3$ | $10^3$ | $a_i=b_i$ |
| 8~9 | $10^3$ | $10^9$ | 无 |
| 10 | 30 | $10^4$ | 无 |
| 11~12 | $10^4$ | $10^4$ | 无 |
| 13 | $10^4$ | $10^4$ | $a_i=b_i-1$ |
| 14~15 | $10^4$ | $10^9$ | 无 |
| 16 | $10^5$ | $10^5$ | $a_i=b_i-1$ |
| 17 | $10^5$ | $10^5$ | 无 |
| 18~20 | $10^5$ | $10^9$ | 无 |