题目描述

在二维平面上有 $\red{N }$个点，从$\red{(x1,y1)}$到$\red{(x2,y2)}$的代价为$\red{|x1-x2|+|y1-y2|}$。

求从 $\red{1 }$号点出发，按从 $\red{1 }$到 $\red{N }$的顺序依次到达每个点的最小总代价。

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

输入格式

第一行 $\red{N,K(2<=N<=500,0<=K<=N-2)}$

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

输出格式

输出最小代价。

样例

输入样例

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

输出样例

3