Zmęczony ciągłą nauką algorytmów 경근 pomyślał, że dobrze byłoby odpocząć kilka dni w innym świecie. Pewnego dnia 상수 powiedział mu, gdzie znajdują się drzwi do innego świata, więc tam poszedł. Drzwi były zamknięte i miały wielki zamek z pokrętłami, którym można było je otworzyć.

Zamek składa się z $M$ pokręteł jedno nad drugim. Każde ma $R$ pól i można je obracać w lewo lub prawo o całe pola. Pole może zawierać kropkę lub być puste. Każde pokrętło ma co najmniej jedną kropkę. Drzwi otworzą się, jeśli po obrotach w pewnym miejscu wszystkie pola w jednej pionowej kolumnie będą miały kropki. Pokrętła obracają się niezależnie. Są bardzo ciężkie, więc chcemy zminimalizować łączną liczbę pól obrotu.

Powyższy rysunek pokazuje przykład. Jeden z optymalnych sposobów to obrócić pierwsze pokrętło od góry o jedno pole w lewo, drugie o dwa pola w lewo, trzecie o jedno pole w prawo, a czwarte pozostawić bez zmian, co daje łącznie 4 pola.

Napisz program, który dla rozmiaru pokręteł i pozycji kropek wyznaczy sposób otwarcia drzwi przy minimalnym łącznym obrocie. Pozycje kropek to pary numeru pokrętła i numeru pola. Górne pokrętło ma numer 0, a numery rosną o 1 w dół, więc dolne ma numer $M-1$. Pola w dowolnej wspólnej pozycji (w jednej pionowej kolumnie) otrzymują numer 0. Numery rosną o 1 w prawo, a na lewo od pola 0 jest pole $R-1$. Żadne dane kropki nie mają tych samych współrzędnych.

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

$M$ to liczba pokręteł, a $R$ to liczba pól na każdym. $P$ jest tablicą $N$ par wartości int. Pierwsza liczba w parze to numer pokrętła, a druga to numer pola. Współrzędne się nie powtarzają. findMinClicks() musi zwrócić najmniejszą łączną liczbę pól, o które trzeba obrócić pokrętła, aby otworzyć drzwi.

Szczegóły implementacji

Należy przesłać dokładnie jeden plik o nazwie dial.cpp, implementujący następującą funkcję.

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

Funkcja ma działać jak opisano powyżej. Można tworzyć i używać inne funkcje wewnętrzne. Kod nie może wykonywać operacji wejścia/wyjścia ani odwoływać się do innych plików.

Przykładowy program oceniający

Dostarczony program oceniający odczytuje wejście w następującym formacie.

• Wiersz 1: liczby całkowite $N$, $M$, $R$.
• Wiersze od 2 do $N+1$: liczby całkowite $D_i$, $C_i$.

Tutaj $(D_i,C_i)$ są współrzędnymi kropki $i$. Program oceniający wypisuje w jednym wierszu wartość zwróconą przez findMinClicks().

Ograniczenia

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

Podzadania

Podzadanie 1 (10 punktów)

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

Podzadanie 2 (15 punktów)

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

Podzadanie 3 (16 punktów)

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

Podzadanie 4 (109 punktów)

Brak dodatkowych ograniczeń.

Przykład

Wejście 1

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

Poniżej pokazano przykładowe wykonanie kodu dla powyższego wejścia.