Cansado de estudar algoritmos continuamente, 경근 pensou que seria bom descansar alguns dias noutro mundo. Um dia, 상수 disse-lhe onde havia uma porta para outro mundo e ele foi até lá. A porta estava trancada e tinha uma grande fechadura de discos que a podia abrir.

A fechadura consiste em $M$ discos empilhados verticalmente. Cada disco tem $R$ células e pode rodar para a esquerda ou direita por células inteiras. Cada célula pode ou não ter um ponto. Cada disco tem pelo menos um ponto. A porta abre se, após as rotações, existir uma posição em que todas as células de uma coluna vertical tenham um ponto. Os discos rodam independentemente. Como são muito pesados e difíceis de rodar, queremos minimizar a soma das células percorridas nas rotações.

A figura acima mostra um exemplo. Uma solução ótima é rodar o primeiro disco a contar de cima uma célula para a esquerda, o segundo duas para a esquerda, o terceiro uma para a direita e não rodar o quarto, num total de 4 células.

Escreva um programa que, dados os tamanhos dos discos e as posições dos pontos, determine como abrir a porta com a rotação total mínima. As posições são pares do número do disco e do número da célula. O disco superior tem número 0 e os números aumentam de um em um para baixo, sendo o inferior $M-1$. As células de qualquer posição comum (numa coluna vertical) recebem o número 0. Os números aumentam de um em um para a direita, e à esquerda da célula 0 fica a célula $R-1$. Não existem pontos com coordenadas coincidentes.

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

$M$ é o número de discos e $R$ o número de células em cada um. $P$ é um vetor de $N$ pares de valores int. O primeiro número de cada par é o número do disco e o segundo é o da célula. As coordenadas não se repetem. findMinClicks() deve devolver a menor soma de células percorridas nas rotações para abrir a porta.

Detalhes de implementação

Deve submeter exatamente um ficheiro chamado dial.cpp que implemente a função seguinte.

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

A função deve comportar-se como descrito acima. Pode criar outras funções para uso interno. O código submetido não pode realizar entrada/saída nem aceder a outros ficheiros.

Avaliador de exemplo

O avaliador fornecido lê a entrada no formato seguinte.

• Linha 1: inteiros $N$, $M$, $R$.
• Linhas de 2 a $N+1$: inteiros $D_i$, $C_i$.

Aqui, $(D_i,C_i)$ são as coordenadas do ponto $i$. O avaliador imprime numa linha o valor devolvido por findMinClicks().

Restrições

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

Subtarefas

Subtarefa 1 (10 pontos)

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

Subtarefa 2 (15 pontos)

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

Subtarefa 3 (16 pontos)

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

Subtarefa 4 (109 pontos)

Sem restrições adicionais.

Exemplos

Entrada 1

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

Abaixo mostra-se uma execução do código para a entrada acima.