Un peu fatigué d'étudier sans cesse les algorithmes, 경근 pensa qu'il serait agréable de se reposer quelques jours dans un autre monde. Un jour, 상수 lui indiqua où se trouvait une porte vers un autre monde, et il s'y rendit. La porte était verrouillée et munie d'une grande serrure à cadrans permettant de l'ouvrir.

La serrure comporte $M$ cadrans superposés. Chacun possède $R$ cases et peut tourner à gauche ou à droite d'un nombre entier de cases. Une case peut contenir un point ou non. Chaque cadran possède au moins un point. La porte s'ouvre si, après les rotations, toutes les cases d'une même colonne verticale contiennent un point à une certaine position. Les cadrans tournent indépendamment. Ils sont très lourds et difficiles à tourner, donc on veut minimiser la somme des nombres de cases parcourues.

La figure ci-dessus montre un exemple. Une méthode optimale consiste à tourner le premier cadran depuis le haut d'une case à gauche, le deuxième de deux cases à gauche, le troisième d'une case à droite et à laisser le quatrième immobile, soit 4 cases au total.

Écrivez un programme qui, à partir de la taille des cadrans et des positions des points, détermine comment ouvrir la porte avec la rotation totale minimale. Les positions sont des couples formés d'un numéro de cadran et d'un numéro de case. Le cadran supérieur porte le numéro 0, puis les numéros augmentent de 1 vers le bas, jusqu'à $M-1$. Les cases d'une position commune quelconque (dans une colonne verticale) portent le numéro 0. Les numéros augmentent de 1 vers la droite ; à gauche de la case 0 se trouve la case $R-1$. Aucun point donné n'a les mêmes coordonnées qu'un autre.

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

$M$ est le nombre de cadrans et $R$ le nombre de cases par cadran. $P$ est un tableau de $N$ couples de valeurs int. Le premier nombre d'un couple est le numéro du cadran, le second celui de la case. Aucune coordonnée n'est répétée. findMinClicks() doit renvoyer la somme minimale des nombres de cases de rotation permettant d'ouvrir la porte.

Détails d'implémentation

Vous devez soumettre exactement un fichier nommé dial.cpp implémentant la fonction suivante.

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

Cette fonction doit se comporter comme décrit ci-dessus. Vous pouvez créer d'autres fonctions utilisées en interne. Le code soumis ne doit effectuer aucune entrée/sortie ni accéder à d'autres fichiers.

Évaluateur fourni

L'évaluateur fourni lit l'entrée au format suivant.

• Ligne 1 : entiers $N$, $M$, $R$.
• Lignes 2 à $N+1$ : entiers $D_i$, $C_i$.

Ici, $(D_i,C_i)$ sont les coordonnées du point $i$. L'évaluateur affiche sur une ligne la valeur renvoyée par findMinClicks().

Contraintes

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

Sous-tâches

Sous-tâche 1 (10 points)

• $1\le N\le5\,000$, $1\le R\le5\,000$.

Sous-tâche 2 (15 points)

• $1\le M\le5\,000$, $1\le R\le5\,000$.

Sous-tâche 3 (16 points)

• $1\le N\le5\,000$.

Sous-tâche 4 (109 points)

Aucune contrainte supplémentaire.

Exemples

Entrée 1

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

Une exécution d'exemple de votre code sur l'entrée ci-dessus est présentée ci-dessous.