Niezadowolony ze zdrowia krów Farmer John zapisuje je na różne ćwiczenia. Jego nagradzana krowa Bessie chodzi na kurs biegania i ma w końcu przebiec maraton przez centrum pobliskiego miasta!

Trasa ma $N$ punktów kontrolnych, $3 \leq N \leq 500$, odwiedzanych kolejno. Punkt 1 to start, a $N$ to meta. Bessie powinna odwiedzić wszystkie, lecz z lenistwa chce pominąć do $K$ punktów, przy $K<N$, aby skrócić drogę. Nie może pominąć 1 ani $N$, bo byłoby to zbyt widoczne.

Wyznacz minimalny dystans przy pominięciu do $K$ punktów.

Ulice centrum tworzą siatkę, więc odległość między $(x1, y1)$ i $(x2, y2)$ wynosi $|x1-x2| + |y1-y2|$.

Wejście

Pierwszy wiersz podaje $N$ i $K$.

Kolejne $N$ wierszy zawiera liczby całkowite $x$ i $y$ oddzielone spacją, współrzędne punktu ($-1000 \leq x \leq 1000,$ $-1000 \leq y \leq 1000$). Punkty podane są w kolejności odwiedzania. Trasa może wielokrotnie się przecinać, a kilka punktów może leżeć w jednym miejscu. Pominięcie takiego punktu pomija tylko jedno jego wystąpienie, nie wszystkie punkty w tym miejscu.

Wyjście

Wypisz minimalny dystans przy pominięciu do $K$ punktów. W przykładzie pominięcie $(8, 3)$ i $(10, -5)$ daje minimalną długość całkowitą 4.

Przykład

Wejście 1

5 2
0 0
8 3
1 1
10 -5
2 2

Wyjście 1

4

Autor zadania: Nick Wu, 2014