题目描述

题目译自 2020년도 국제정보올림피아드 대표학생 선발고사 - 2차 선발고사 T1 「마법의 다이얼」

在持续的算法学习中感到疲惫的京根，想去另一个世界休息几天。有一天，他听说了一个通往另一个世界的门的位置，于是他去了那里。那里有一扇通往另一个世界的门，但门被锁住了，门上有一个巨大的转盘锁。

这个锁由上下排列的 $M$ 个转盘组成。每个转盘有 $R$ 个格子，可以左右旋转到不同的格子。每个格子上可能有一个点，也可能没有点。每个转盘至少有一个点。通过旋转转盘，使得在某个位置上所有格子都垂直对齐有点，门就会打开。每个转盘可以单独旋转。由于转盘非常重，旋转起来很费力，所以希望旋转的总格子数最少。

上图展示了一个转盘的例子。最佳方法之一是：将第一个转盘向左旋转一格，第二个转盘向左旋转两格，第三个转盘向右旋转一格，第四个转盘不旋转，总共旋转 $4$ 格。

给定转盘的大小和点的位置，编写一个程序，计算最少需要旋转多少格才能打开门。点的位置由转盘编号和格子编号的坐标表示。最上面的转盘是 $0$ 号转盘，向下编号依次增加，最下面的转盘是 $M-1$ 号转盘。为了确定格子编号，任意相同位置的（即垂直对齐的）格子编号为 $0$，向右编号依次增加。$0$ 号格子的左边是 $R-1$ 号格子。给定的点的坐标不会重复。

实现细节

你需要实现以下函数：

long long findMinClicks(int M, int R, vector< pair<int, int> > P);

• 参数 $M$ 是转盘的数量。
• 参数 $R$ 是每个转盘的格子数。
• 参数 $P$ 是一个包含 $N$ 个整数对的数组。每个整数对的第一个数是转盘编号，第二个数是格子编号。给定的点的坐标不会重复。
• 函数 findMinClicks() 返回打开门所需的最少旋转格子数。

你需要提交一个名为 dial.cpp 的文件，该文件中实现以下函数：

long long findMinClicks(int M, int R, vector< pair<int, int> > P);

该函数应按照上述描述工作。当然，你可以创建其他函数并在内部使用。提交的代码不应执行输入输出操作或访问其他文件。

示例评测程序

示例评测程序按以下格式读取输入：

• 第 $1$ 行：整数 $N$ $M$ $R$
• 第 $2 \sim N+1$ 行：整数 $D_{i}$ $C_{i}$，其中 $(D_{i}, C_{i})$ 是第 $i$ 个点的坐标。

示例评测程序将输出你的代码中 findMinClicks() 函数返回的值。

样例

输入

7 4 20
1 3
0 2
2 6
3 8
3 1
2 0
1 8

输出

4

以下是样例中函数调用及其结果的顺序：

数据范围与提示

对于所有输入数据，满足：

• $1 \leq R \leq 10^{9}$
• $1 \leq N \leq \min(MR, 5\cdot 10^5)$
• $1 \leq M \leq N$

详细子任务附加限制及分值如下表所示。