Insatisfeito com a saúde das vacas, Farmer John as inscreve em várias atividades físicas. Sua vaca premiada Bessie faz aulas de corrida e deverá correr uma maratona pelo centro da cidade próxima à fazenda!

O percurso tem $N$ pontos de controle, $3 \leq N \leq 500$, visitados em ordem. O ponto 1 é a partida e o $N$ a chegada. Bessie deveria visitar todos, mas, preguiçosa, decide pular até $K$ deles, com $K<N$, para encurtar o caminho. Não pode pular 1 nem $N$, pois seria evidente demais.

Encontre a menor distância que ela deve correr pulando até $K$ pontos.

As ruas do centro formam uma grade, então a distância entre $(x1, y1)$ e $(x2, y2)$ é $|x1-x2| + |y1-y2|$.

Entrada

A primeira linha dá $N$ e $K$.

As próximas $N$ linhas contêm os inteiros $x$ e $y$ separados por espaço, as coordenadas de um ponto ($-1000 \leq x \leq 1000,$ $-1000 \leq y \leq 1000$). Os pontos vêm na ordem de visita. O percurso pode se cruzar várias vezes e pontos podem ocupar o mesmo local. Ao pular um deles, Bessie pula apenas aquela ocorrência, não todos os pontos naquele local.

Saída

Imprima a menor distância pulando até $K$ pontos. No exemplo, pular $(8, 3)$ e $(10, -5)$ dá a distância total mínima 4.

Exemplos

Entrada 1

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

Saída 1

4

Autor: Nick Wu, 2014