题目内容

快递员初始位于二维平面坐标原点 $(0,0)$。现有 $N$ 个快递包裹需要派送，第 $i$ 个包裹的坐标为 $(x_i,y_i)$，坐标单位为公里。为了减少上门配送次数，公司要求先使用 K-Means 聚类将所有包裹划分为 $K$ 个社区簇，快递员只需将货物送至每个社区簇的聚类中心。

配送时，快递员从原点出发，按照聚类中心到原点的距离由近到远依次访问所有聚类中心，最后返回原点。已知快递员的平均行驶速度为 $\text{speed}$ km/h，请计算完成全部配送所需的总时间，单位为秒，结果向下取整。

两个二维点 $a=(x_a,y_a)$ 与 $b=(x_b,y_b)$ 之间的欧氏距离定义为：

K-Means 聚类的执行规则如下：

• 实际聚类中心数量为 $M=\min(K,N)$。
• 种子点初始化：将所有包裹按到原点的距离升序排序；若距离相同，按输入顺序升序排序。取排序后的前 $M$ 个点作为初始聚类中心。
• 分配：对每个包裹，计算它到当前 $M$ 个聚类中心的欧氏距离，将其分配到距离最近的中心所对应的簇；若多个中心距离相同，选择编号最小的中心。
• 更新：对每个非空簇，将其聚类中心更新为该簇内所有包裹坐标的算术平均值；若某个簇为空，则保持该簇中心不变。
• 收敛判断：更新后计算所有聚类中心本次移动距离之和。若该和小于 $10^{-4}$，或已经迭代了 50 轮，则停止迭代；否则继续执行分配与更新步骤。

聚类结束后，将所有最终聚类中心按到原点的距离升序排序。快递员的完整访问顺序为：

设该折返路线的总长度为 $d_{\text{total}}$，则所需总时间为：

约束条件

• $1 \le K \le 10$
• $1 \le N \le 100$
• $1 \le \text{speed} \le 100$

输入描述

第一行包含三个由空格分隔的整数：$K$、$N$ 和 $\text{speed}$，分别表示社区个数、快递包裹总数和快递员平均行驶速度（km/h）。

接下来 $N$ 行，每行包含两个实数 $x_i$ 和 $y_i$，表示第 $i$ 个包裹的坐标（公里）。

输出描述

输出一个整数，表示快递员完成全部配送并返回原点所需的总时间（秒，向下取整）。

样例1

输入

1 3 20
3 0
0 4
3 4

输出

1200

说明

K 为 1，N 为 3，因此实际聚类中心数为 1。唯一中心最终为三个包裹坐标的算术平均值 $(2, \frac{8}{3})$。

该中心到原点的距离为 $\sqrt{2^2 + (\frac{8}{3})^2} = \frac{10}{3}$ km。配送路线为原点 $\to$ 中心 $\to$ 原点，总长度 $d_{\text{total}} = 2 \times \frac{10}{3} = \frac{20}{3}$ km。

结合速度 20 km/h，总时间为 $\left\lfloor \frac{20/3 \times 3600}{20} \right\rfloor = 1200$ 秒。因此输出为 1200。

样例2

输入

4 4 10
0 -4
1 0
-3 0
0 2

输出

5702

说明

K 为 4，N 为 4，实际聚类中心数也为 4。每个包裹自身构成一个聚类，最终中心就是 4 个包裹坐标。按到原点的距离升序排序后，访问顺序为 $(1,0)$、$(0,2)$、$(-3,0)$、$(0,-4)$。

路径长度为：原点到 $(1,0)$ 为 $1$，$(1,0)$ 到 $(0,2)$ 为 $\sqrt{5}$，$(0,2)$ 到 $(-3,0)$ 为 $\sqrt{13}$，$(-3,0)$ 到 $(0,-4)$ 为 $5$，$(0,-4)$ 返回原点为 $4$。因此总长度 $d_{\text{total}} = 1 + \sqrt{5} + \sqrt{13} + 5 + 4 \approx 15.841619$ km。

速度 10 km/h 时，总时间为 $\left\lfloor \frac{15.841619 \times 3600}{10} \right\rfloor = 5702$ 秒。因此输出为 5702。

样例3

输入

3 1 7
6 8

输出

10285

说明

K 为 3，N 为 1，因为包裹数量小于社区数量，实际聚类中心数为 1。唯一包裹坐标 $(6,8)$ 就是最终中心。

该中心到原点的距离为 $\sqrt{6^2 + 8^2} = 10$ km，折返路线总长度 $d_{\text{total}} = 2 \times 10 = 20$ km。

速度 7 km/h 时，总时间为 $\left\lfloor \frac{20 \times 3600}{7} \right\rfloor = 10285$ 秒。因此输出为 10285。