题目描述

给定 $N$ 个按顺序排列的检查点，每个检查点有坐标 ($x_i, y_i$)。

需要从第 $1$ 个检查点出发，按顺序访问到第 $N$ 个检查点，其中可以跳过最多 $K$ 个 检查点(但不能跳过第 $1$ 个和第 $N$ 个检查点)。

求从第 $1$ 个检查点到第 $N$ 个检查点的最短路径长度。

路径长度定义为相邻访问的检 查点之间的曼哈顿距离(即 $|x_i − x_j | + |y_i − y_j |$)之和。

输入格式

第一行:两个整数 $N$ 和 $K$，表示检查点总数和最多可跳过的检查点数。

接下来 $N$ 行:每行两个整数 $x_i$ 和 $y_i$，表示第 $i$ 个检查点的坐标。

输出格式

一个整数，表示最短路径长度。

样例 1 输入

5 2 
0 0 
8 3  
1 1
10 ‐5 
2 2

样例 1 输出

4

数据范围

对于 $100\%$ 的数据满足:$3 ≤ N ≤ 500$,$K < N$,$−1000 ≤ x ≤ 1000$,$−1000 ≤ y ≤ 1000$