Mécontent de la santé de ses vaches, Farmer John les inscrit à diverses activités sportives. Sa vache primée Bessie suit un cours de course à pied et devra finalement courir un marathon dans le centre de la ville proche de la ferme !

Le parcours comporte $N$ points de contrôle, $3 \leq N \leq 500$, à visiter dans l’ordre. Le point 1 est le départ et le point $N$ l’arrivée. Bessie devrait tous les visiter, mais, paresseuse, décide d’en sauter jusqu’à $K$, avec $K<N$, pour raccourcir le trajet. Elle ne peut sauter ni 1 ni $N$, car cela se remarquerait trop.

Trouvez la distance minimale qu’elle doit courir en sautant jusqu’à $K$ points.

Les rues du centre forment une grille : la distance entre $(x1, y1)$ et $(x2, y2)$ est $|x1-x2| + |y1-y2|$.

Entrée

La première ligne donne $N$ et $K$.

Les $N$ lignes suivantes contiennent chacune les entiers $x$ et $y$ séparés par un espace, les coordonnées d’un point ($-1000 \leq x \leq 1000,$ $-1000 \leq y \leq 1000$). Les points sont donnés dans l’ordre de visite. Le parcours peut se croiser plusieurs fois et des points peuvent partager le même emplacement. Sauter un tel point ne saute qu’une occurrence, pas tous les points à cet endroit.

Sortie

Affichez la distance minimale en sautant jusqu’à $K$ points. Dans l’exemple, sauter $(8, 3)$ et $(10, -5)$ donne la distance totale minimale 4.

Exemples

Entrée 1

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

Sortie 1

4

Auteur : Nick Wu, 2014