A2188 | [USACO14DEC] Marathon S

【题目描述】

由于对他的奶牛的健康状况不佳而感到不满，牧场主约翰让它们参加各种各样的体育健身活动。最让他感到自豪的奶牛是 Bessie，她将参加约翰牧场附近城市里的马拉松比赛！

马拉松比赛有 $N$ 个检查点 $(3\leq N\leq 500)$ ，需要按顺序访问。检查点 $1$ 是起点，检查点 $N$ 是终点。Bessie 应该按顺序一一访问所有的这些检查点，但由于她是一头懒惰的牛（懒惰竟然还选择跑马拉松！），于是她决定跳过 $K(K<N)$ 个检查点以缩小她的赛程。但她不能跳过第 $1$ 个和第 $N$ 个检查点，因为这样太明显了。

请你帮助 Bessie 计算出跳过中间的 $K$ 个检查点后她最少要跑多少距离。

注意：由于街道是网格状的，我们用坐标来表示点的位置。但是 $(x_1,y_1),(x_2,y_2)$ 两点间的距离应为 $|x_1-x_2|+|y_1-y_2|$，这种测量距离的方法被称为“曼哈顿”距离，这是因为在市中心的网格路中，你可以沿平行于 $x$ 轴或 $y$ 轴的方向走，但不能沿直线到达。

第一行：两个正整数 $N$ 和 $K$。

第 $2$ 行到第 $N+1$ 行，每行两个整数$x,y (-1000\leq x\leq 1000,-1000\leq y\leq 1000)$。

这里给出了检查点的顺序，她必须按顺序访问。注意：可能会有几个检查点出现在同一位置，Bessie 跳过这样的检查点时，相当于只跳过其中的一个检查点。

输出跳过某一个检查点后 Bessie 可以跑的最短距离。