路段

题目描述

一次旅行将依次经过 $n$ 个检查点，第 $i$ 个检查点的坐标为 $(x_i,y_i)$。

从检查点 $i$ 到检查点 $i+1$ 的路程为两点间的曼哈顿距离：

现在你需要取消恰好连续的 $K$ 个中间检查点。设被取消的检查点编号为 $l,l+1,\dots,l+K-1$，则旅行行会从检查点 $l-1$ 直接前往检查点 $l+K$，其余检查点的先后顺序不变。

检查点 $1$ 和检查点 $n$ 不能被取消。

请你求出取消检查点后，旅行的最短总路程。

输入格式

从文件 road.in 中读入数据。

第一行输入两个整数 $n,K$。

接下来 $n$ 行，第 $i$ 行输入两个整数 $x_i,y_i$，表示第 $i$ 个检查点的坐标。

输出格式

输出到文件 road.out 中。

输出一个整数，表示取消恰好 $K$ 个中间检查点后，旅行的最短总路程。

样例输入

6 2
0 0
2 0
2 3
5 3
5 1
8 1

样例输出

9

样例解释

取消检查点 $3,4$ 后，旅行路线变为 $1 \to 2 \to 5 \to 6$，总路程为 $2 + 4 + 3 = 9$。

数据规模与约定

对于所有数据：

• $3 \le n \le 5 \times 10^5$；
• $1 \le K \le n-2$；
• $-10^9 \le x_i,y_i \le 10^9$。

检查点坐标不要求互不相同。