Cansado de estudiar algoritmos continuamente, 경근 pensó que sería agradable descansar unos días en otro mundo. Un día, 상수 le dijo dónde había una puerta a otro mundo y fue allí. La puerta estaba cerrada y tenía una gran cerradura de diales que permitía abrirla.

La cerradura consta de $M$ diales apilados verticalmente. Cada uno tiene $R$ casillas y puede girarse a izquierda o derecha por casillas enteras. Cada casilla puede contener un punto o no. Cada dial tiene al menos un punto. La puerta se abre si, tras los giros, en alguna posición todas las casillas de una columna vertical tienen un punto. Los diales giran independientemente. Son muy pesados y difíciles de girar, por lo que queremos minimizar la suma de casillas giradas.

La figura anterior muestra un ejemplo. Una solución óptima consiste en girar el primer dial desde arriba una casilla a la izquierda, el segundo dos a la izquierda, el tercero una a la derecha y dejar el cuarto quieto, para un total de 4 casillas.

Escribe un programa que, dados los tamaños de los diales y las posiciones de los puntos, determine cómo abrir la puerta con el mínimo giro total. Las posiciones son pares de número de dial y número de casilla. El dial superior es el 0 y los números aumentan de uno en uno hacia abajo, siendo el inferior el $M-1$. Se asigna el número 0 a las casillas de cualquier posición común (una columna vertical). Los números aumentan de uno en uno hacia la derecha, y a la izquierda de la casilla 0 está la $R-1$. No hay puntos con coordenadas coincidentes.

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

$M$ es el número de diales y $R$ el número de casillas de cada uno. $P$ es un arreglo de $N$ pares de valores int. El primer número de cada par es el número de dial y el segundo el de casilla. No se repiten coordenadas. findMinClicks() debe devolver la mínima suma de casillas que deben girarse para abrir la puerta.

Detalles de implementación

Debes enviar exactamente un archivo llamado dial.cpp que implemente la siguiente función.

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

La función debe comportarse como se describió arriba. Puedes crear otras funciones para uso interno. El código enviado no debe realizar entrada/salida ni acceder a otros archivos.

Evaluador de ejemplo

El evaluador proporcionado lee la entrada con el siguiente formato.

• Línea 1: enteros $N$, $M$, $R$.
• Líneas de la 2 a la $N+1$: enteros $D_i$, $C_i$.

Aquí, $(D_i,C_i)$ son las coordenadas del punto $i$. El evaluador imprime en una línea el valor devuelto por findMinClicks().

Restricciones

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

Subtareas

Subtarea 1 (10 puntos)

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

Subtarea 2 (15 puntos)

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

Subtarea 3 (16 puntos)

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

Subtarea 4 (109 puntos)

Sin restricciones adicionales.

Ejemplos

Entrada 1

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

A continuación se muestra una ejecución de tu código para la entrada anterior.