Farmer John, descontento con la salud de sus vacas, las inscribe en distintas actividades físicas. Su preciada vaca Bessie toma clases de carrera y finalmente deberá correr una maratón por el centro de la ciudad cercana a la granja.

El recorrido tiene $N$ puntos de control, $3 \leq N \leq 500$, que se visitan en orden. El punto 1 es la salida y el $N$ la meta. Bessie debería visitarlos todos, pero por pereza decide saltarse hasta $K$, con $K<N$, para acortar el viaje. No puede saltarse 1 ni $N$, pues sería demasiado evidente.

Encuentra la mínima distancia que debe correr al saltarse hasta $K$ puntos.

Las calles del centro forman una cuadrícula, así que la distancia entre $(x1, y1)$ y $(x2, y2)$ es $|x1-x2| + |y1-y2|$.

Entrada

La primera línea da $N$ y $K$.

Las siguientes $N$ líneas contienen los enteros $x$ y $y$ separados por un espacio, las coordenadas de un punto ($-1000 \leq x \leq 1000,$ $-1000 \leq y \leq 1000$). Se dan en orden de visita. El recorrido puede cruzarse varias veces y varios puntos pueden compartir ubicación. Saltarse uno de ellos solo omite esa aparición, no todos los puntos de esa ubicación.

Salida

Imprime la mínima distancia al saltarse hasta $K$ puntos. En el ejemplo, omitir $(8, 3)$ y $(10, -5)$ da la mínima distancia total de 4.

Ejemplos

Entrada 1

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

Salida 1

4

Autor: Nick Wu, 2014