题目描述

题目译自 BalticOI 2023 Day1「Astronomer」

一位天文学家酷爱观星。特别是当用望远镜同时观察 $k$ 颗恒星，他感到无比愉悦。建造一个半径为 $r$ 的望远镜需要花费 $t \cdot r$ 克朗。新造的望远镜将精确地指向原点 $(0, 0)$。将它移动到其他地方也需要花费精力；将望远镜移动 $d$ 个单位的距离需要花费 $s \cdot d$ 克朗。天文学家可以从望远镜指向的地方观察到距离最多为 $r$ 的所有恒星。

建造和移动一台可同时观测 $k$ 颗恒星的望远镜需要多少钱？

所有坐标和距离均在欧几里得平面上。

例子

这个例子有 $n=3$ 颗恒星，位于 $(0,0),(2,0)$ 和 $(3,1)$。阴影部分展示了一个半径为 $1$ 并指向 $(1,0)$ 的望远镜，它覆盖了两颗恒星；这将花费 $s+t$ 克朗，并且是样例 $3$ 的最优解。这个图片同样展示了样例 $1,2,4$ 的最优解。

输入格式

第一行四个整数 $k,n,s,t$，分别表示天文学家想要观测的恒星数，天空中所有的恒星总数，移动花费 $s$ 和建造花费 $t$。

接下来 $n$ 行，第 $i$ 行包含两个整数 $x_i,y_i$，表示第 $i$ 颗恒星的坐标。

输出格式

输出一个实数：天文学家最小要花费的克朗数。

2 3 1000 500
0 0
2 0
3 1

1000.0

2 3 500 3000
0 0
2 0
3 1

3387.277541898787

2 3 250 750
0 0
2 0
3 1

1000.0

2 3 0 500
0 0
2 0
3 1

353.5533905932738

3 4 0 10
0 0
10 0
5 10
5 5

50.0

数据范围与提示

对于所有数据，满足：

• $1\le k\le n\le 700$
• $x_i,y_i\in\{-10^9,\ldots,10^9\}$ 对于所有 $i\in\{1,\ldots,n\}$
• $s,t\in\{0,\ldots,10^9\}$
• 如果你的输出与答案之间的绝对误差或相对误差在 $\varepsilon=10^{-6}$ 之内，你的输出将被判为正确

详细子任务附加限制及分值如下表所示。

注：由于 LibreOJ 实现限制，子任务 $6$ 中 $\varepsilon$ 的取值仍为 $10^{-6}$。也就是这组子任务没有实现附加限制的测评要求。