Vom ständigen Lernen von Algorithmen etwas erschöpft, dachte 경근, ein paar Tage Erholung in einer anderen Welt wären schön. Eines Tages erfuhr er von 상수, wo sich eine Tür in eine andere Welt befand, und ging dorthin. Die Tür war verschlossen und hatte ein großes Drehscheibenschloss, mit dem sie geöffnet werden konnte.

Das Schloss besteht aus $M$ übereinander angeordneten Drehscheiben. Jede hat $R$ Felder und kann um ganze Felder nach links oder rechts gedreht werden. Ein Feld kann einen Punkt enthalten oder leer sein. Jede Scheibe hat mindestens einen Punkt. Die Tür öffnet sich, wenn nach den Drehungen an irgendeiner Position alle Felder einer senkrechten Spalte einen Punkt enthalten. Die Scheiben drehen sich unabhängig. Sie sind sehr schwer und mühsam zu drehen, daher soll die Summe der gedrehten Feldanzahlen minimiert werden.

Die obige Abbildung zeigt ein Beispiel. Eine optimale Methode dreht die erste Scheibe von oben ein Feld nach links, die zweite zwei Felder nach links, die dritte ein Feld nach rechts und die vierte gar nicht, insgesamt also 4 Felder.

Schreibe ein Programm, das anhand der Scheibengrößen und Punktpositionen bestimmt, wie die Tür mit minimaler Gesamtdrehung geöffnet wird. Punktpositionen sind Paare aus Scheibennummer und Feldnummer. Die oberste Scheibe hat Nummer 0, nach unten steigen die Nummern jeweils um 1, sodass die unterste Nummer $M-1$ hat. Felder an einer beliebigen gemeinsamen Position (in einer senkrechten Spalte) erhalten Nummer 0. Nach rechts steigen die Nummern jeweils um 1; links von Feld 0 liegt Feld $R-1$. Keine gegebenen Punkte haben dieselben Koordinaten.

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

$M$ ist die Anzahl der Scheiben, $R$ die Anzahl der Felder pro Scheibe. $P$ ist ein Array von $N$ Paaren von int-Werten. Die erste Zahl eines Paars ist die Scheibennummer, die zweite die Feldnummer. Keine Koordinaten stimmen überein. findMinClicks() muss die minimale Gesamtsumme gedrehter Felder zurückgeben, mit der die Tür geöffnet werden kann.

Implementierungsdetails

Du musst genau eine Datei namens dial.cpp einreichen, die folgende Funktion implementiert.

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

Die Funktion muss sich wie oben beschrieben verhalten. Weitere Funktionen dürfen intern erstellt und verwendet werden. Der eingereichte Code darf keine Ein-/Ausgabe durchführen und nicht auf andere Dateien zugreifen.

Beispiel-Bewertungsprogramm

Das bereitgestellte Bewertungsprogramm liest die Eingabe im folgenden Format.

• Zeile 1: ganze Zahlen $N$, $M$, $R$.
• Zeilen 2 bis $N+1$: ganze Zahlen $D_i$, $C_i$.

Dabei sind $(D_i,C_i)$ die Koordinaten von Punkt $i$. Das Bewertungsprogramm gibt den Rückgabewert von findMinClicks() in einer Zeile aus.

Beschränkungen

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

Teilaufgaben

Teilaufgabe 1 (10 Punkte)

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

Teilaufgabe 2 (15 Punkte)

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

Teilaufgabe 3 (16 Punkte)

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

Teilaufgabe 4 (109 Punkte)

Keine zusätzlichen Beschränkungen.

Beispiele

Eingabe 1

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

Unten ist eine Beispielausführung des Codes für die obige Eingabe dargestellt.