该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。
路段
题目描述
一次旅行将依次经过 n 个检查点，第 i 个检查点的坐标为 (xi,yi)。
从检查点 i 到检查点 i+1 的路程为两点间的曼哈顿距离：
∣xi−xi+1∣+∣yi−yi+1∣
现在你需要取消恰好连续的 K 个中间检查点。设被取消的检查点编号为 l,l+1,…,l+K−1，则旅行行会从检查点 l−1 直接前往检查点 l+K，其余检查点的先后顺序不变。
检查点 1 和检查点 n 不能被取消。
请你求出取消检查点后，旅行的最短总路程。
输入格式
从文件 road.in 中读入数据。
第一行输入两个整数 n,K。
接下来 n 行，第 i 行输入两个整数 xi,yi，表示第 i 个检查点的坐标。
输出格式
输出到文件 road.out 中。
输出一个整数，表示取消恰好 K 个中间检查点后，旅行的最短总路程。
样例输入
6 2
0 0
2 0
2 3
5 3
5 1
8 1
样例输出
9
样例解释
取消检查点 3,4 后，旅行路线变为 1→2→5→6，总路程为 2+4+3=9。
数据规模与约定
对于所有数据：
- 3≤n≤5×105；
- 1≤K≤n−2；
- −109≤xi,yi≤109。
检查点坐标不要求互不相同。
| 子任务 |
分值 |
限制 |
测试点 |
| 1 |
20 |
n≤20 |
01–05 |
| 2 |
n≤2000 |
06–10 |
| 3 |
K≤20 |
11–15 |
| 4 |
16 |
n≤104 |
16–19 |
| 5 |
12 |
n≤105 |
20–22 |
| 6 |
n≤5∗105 |
23–25 |
