Problem 1: Magic Dial

Kyung-geun, exhausted from his continuous study of algorithms, thought it would be nice to take a break in another world for a few days. One day, he heard from Sang-soo about a place where a door to another world exists, and he went there. There was a door to another world, but it was locked, and there was a large dial-type lock that could open it.

The lock is made of $M$ dials stacked vertically. Each dial has $R$ slots and can be rotated left or right to align the slots. Each slot on a dial may or may not have a dot. Each dial has at least one dot. It is said that the door opens if you rotate the dials such that at any position, there is a dot in every slot vertically. Each dial rotates independently. Since the dials are very heavy and difficult to turn, you want to minimize the total number of slots rotated.

The figure above shows an example of the dials. One of the best ways is to rotate the first dial from the top one slot to the left, the second dial two slots to the left, the third dial one slot to the right, and not rotate the fourth dial, for a total of 4 slots rotated.

Write a program that takes the size of the dials and the positions of the dots as input and finds the way to rotate the dials with the minimum number of slots so that the door opens. The positions of the dots are given as coordinates, which are pairs of dial numbers and slot numbers. The topmost dial is dial 0. As you go down, the dial number increases by 1. The bottommost dial will be dial $M-1$. To determine the slot number, choose any arbitrary position (i.e., a vertical line) and label those slots as 0. As you move to the right, the slot number increases by 1. To the left of slot 0, there will be slot $R-1$. The given coordinates of the dots do not overlap.

• long long findMinClicks(int M, int R, vector<pair<int, int>> P): $M$ is the number of dials. $R$ is the number of slots per dial. $P$ is an array of size $N$ containing pairs of integers. The first integer in a pair is the dial number, and the second integer is the slot number. The given coordinates of the dots do not overlap. The findMinClicks() function should return the number of slots rotated in the way that minimizes the total number of slots rotated to open the door.

Implementation Details

You must submit exactly one file named dial.cpp. This file must implement the following function:

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

This function must operate as described above. You may, of course, create other functions to use internally. The submitted code must not perform any input/output operations or access other files.

Grader Example

The provided grader receives input in the following format:

• Line 1: Integers $N, M, R$
• Line 2 ~ $N+1$: Integers $D_i, C_i$

In the above, $(D_i, C_i)$ is the coordinate of the $i$-th dot. The provided grader prints the value returned by your code's findMinClicks() function on a single line.

Constraints

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

Subtasks

• Subtask 1 [10 points]: $1 \le N \le 5,000$, $1 \le R \le 5,000$
• Subtask 2 [15 points]: $1 \le M \le 5,000$, $1 \le R \le 5,000$
• Subtask 3 [16 points]: $1 \le N \le 5,000$
• Subtask 4 [109 points]: No additional constraints beyond the original ones.

Examples

Input 1

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

Output 1

4

Note

The following table shows an execution example based on how your code operates for the input above.