T267929 「GOI-R1」不卜庐

$$\pmb{\color{DarkOrchid}『起死回骸童子，救苦渡厄真君』}$$

不卜庐的七七正打算出门采药，但由于她是僵尸，只能前后左右移动。七七可以看作处在一个平面直角坐标系中，位置为$(x_s, y_s)$。她发现一株药草在 $(x_t, y_t)$ 处，七七想要尽快地采到这株药草。七七在她的位置上发现了一个元素方碑，同时还发现有另外 $n$ 个元素方碑在不同的地方，其中第 $i$ 个元素方碑的坐标在 $(x_i, y_i)$。 七七没有力气了，所以初速为 $0$，但使用一次元素方碑可以让她的速度加 $1$。不过同一个元素方碑是不能连续使用的，七七用了一个元素方碑后，必须要去到另一个元素方碑后才能再回来用原来那个元素方碑。七七的速度最多达到 $m$。七七想知道，她最少花费多久就能采到那株药草。**元素方碑不能移动，所以只有在有元素方碑的坐标上才能够使用。** #### 形式化题意 在一个平面直角坐标系中，起点为 $(x_s, y_s)$，终点为 $(x_t, y_t)$，你只能够向上下左右移动，初始时速度为 $0$。在起点和其他 $n$ 个位置可以使用一次道具使得速度增加一，但是在同一个位置不能连续使用道具，只有在另一个地点使用过道具之后才能够回到当前地点再次使用道具。最多使用$m$次道具。求从起点到终点的最短时间。 **注意：** 当速度为$i$时，$p$秒可以从当前所在坐标$(a, b)$移到$(c, d)$满足$ |a - c| + |b - d| = i * p$（$p$可为浮点数）。

第一行输入 $6$ 个整数，分别是 $n, m, x_s, y_s, x_t, y_t$。 接下来 $n$ 行每行输入两个整数，即第 $i$ 个元素方碑的坐标，分别是 $x_i, y_i$。

输出一个实数，即七七最少花费的时间。

### 数据范围 **本题采用捆绑测试。** | Subtask | $n,m$ | 分数 | | :----------: | :----------: | :----------: | | 1 | $n,m \leq 15$ | $20$ | | 2 | $n \leq 350, m \leq 100$ | $30$ | | 3 | $n \leq 500, m \leq 100$ | $50$ | 对于$100\%$的数据，$-100000 \leq x_i,y_i,x_s,y_s,x_t,y_t \leq 100000$。 本题采用 Special Judge，当输出结果与答案相差小于 $0.01$ 即视作正确。 为减少可能存在的精度问题带来的影响，我们提供了 [分数模板](https://www.luogu.com.cn/paste/rvfzmllo) 供需要的选手使用。**如果您未通过本题且认为自己可能遇到了精度问题，可以尝试使用分数模板。** 但需要注意的是，使用分数模板很可能会带来巨大的常数甚至使得复杂度改变，所以不建议使用。