Minimum Total Rotations to Open the Door

The door is secured by a lock with M vertical rotors, each containing R cells arranged in a circle. Some cells contain a dot and each rotor has at least one dot. The rotors are initially aligned so that the cell labelled 0 on each rotor is in the same vertical column. You may rotate each rotor independently either left or right (cyclically). The goal is to rotate the rotors such that there exists a vertical column where every rotor displays a dot. Since rotating these heavy wheels is tiring, you want to achieve this with a minimum total number of cell rotations.

More formally, for each rotor i (0 ≤ i ≤ M-1), you are given the positions of dots on that rotor (each a value between 0 and R-1). After a rotor is rotated by d steps (negative for left, positive for right), a dot originally at position j moves to position \( (j-d) \mod R \). For a chosen vertical column \( t \) (0 ≤ t ≤ R-1), the cost to align rotor i is the minimum rotation steps needed so that one of its dots ends up at column \( t \); formally, for each dot at position \( j \) on rotor i, the rotation cost is \( \min(|j-t|, R-|j-t|) \). The objective is to select a column \( t \) that minimizes the sum of rotation costs for all rotors.

You are required to implement the following function:

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

where:

• M is the number of rotors.
• R is the number of cells per rotor.
• P is a vector containing pairs of integers, where the first element of each pair is the rotor index and the second element is the cell index at which there is a dot. No coordinate pair is repeated.

The function should return the minimum total number of cell rotations required to align a dot in some vertical column on every rotor.

inputFormat

The input consists of three integers M, R and N on the first line, where M is the number of rotors, R is the number of cells per rotor, and N is the total number of dots. This is followed by N lines, each containing two integers representing a dot's position with the rotor index and the cell index, respectively.

Note: The function you implement should not perform any input/output operations.

outputFormat

Output a single integer representing the minimum total number of cell rotations required to open the door.

sample

4 6 4
0 1
1 2
2 5
3 0

4