该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

在一个二维平面上有N 个点，从(x1,y1)到(x2,y2)的代价为|x1-x2|+|y1-y2|。 求从1 号点出发，按从1 到N 的顺序依次到达每个点的最小总代价。

你有K 次机会可以跳过某个点，不允许跳过1 号点或N 号点。

输入

第一行N,K(2<=N<=500,0<=K<=N-2)

接下来N 行每行两个数(x,y)表示第i 个点的坐标。(-1000 <= x <= 1000, -1000 <= y <= 1000)

输出

一行，一个整数，表示输出最小代价。

样例输入

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

样例输出

4