问题 1：魔法转盘

持续的算法学习让京根感到有些疲惫，他觉得如果能去另一个世界休息几天会很好。某一天，他从常秀那里听说了一个有通往异世界之门的地方，于是前往那里。那里果然有一扇通往异世界的门，但门是锁着的，门上有一个巨大的转盘式密码锁。

这个密码锁由上下共 $M$ 个转盘组成。每个转盘有 $R$ 个格子，可以向左或向右按格子旋转。每个格子上可能有点，也可能没有点。每个转盘上至少有 $1$ 个点。通过旋转转盘，如果能够在某个位置上使得纵向的所有格子上都有点，那么门就会打开。每个转盘都是独立旋转的。由于转盘非常沉重，旋转起来很困难，因此希望最小化旋转的格子数之和。

上图展示了一个转盘的示例。其中一种可能的最优方法是：最上面的第一个转盘向左转 $1$ 格，第二个转盘向左转 $2$ 格，第三个转盘向右转 $1$ 格，第四个转盘不转动，总共旋转 $4$ 格。

给定转盘的大小以及点的位置，请编写程序，找出使门打开所需旋转的最小格子数。点的位置以“转盘编号”和“格子编号”的二元组坐标形式给出。最上面的转盘编号为 $0$，向下每个转盘编号依次增加 $1$，最下面的转盘编号为 $M-1$。

为了确定格子编号，将某一任意的、在竖直方向上对齐的一列格子定义为 $0$ 号格子，向右方向格子编号依次增加 $1$。$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 行到第 $N+1$ 行：整数 $D_i, C_i$

其中 $(D_i, C_i)$ 表示第 $i$ 个点的坐标。评测程序会将你在 findMinClicks() 函数中返回的值输出为一行。

限制

• $1 \le R \le 10^9$
• $1 \le N \le \min(MR, 500000)$
• $1 \le M \le N$

子任务

• 子任务 1 [10 分]：$1 \le N \le 5000$, $1 \le R \le 5000$
• 子任务 2 [15 分]：$1 \le M \le 5000$, $1 \le R \le 5000$
• 子任务 3 [16 分]：$1 \le N \le 5000$
• 子任务 4 [109 分]：除原始限制条件外无额外限制

样例数据

输入：

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

按照上述输入，你的代码的执行示例如下：

findMinClicks( 7, 4, 20, { {1, 3}, {0, 2}, {2, 6}, {3, 8}, {3, 1}, {2, 0}, {1, 8} } )

返回值：

4