题目背景

请使用 C++17 或 C++20 提交本题

你需要在程序开头加入如下代码：

#include <vector>

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

题目译自 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() 返回打开门所需的最少旋转格子数。

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

输入格式

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

• 第 $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$

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

本题满分为 $150$ 分。