故事

AtCoder定期在互联网上直播官方的"A-Da-Coder"节目，以提供最新的消息并与用户互动。为了吸引更多观众，CEO Takahashi决定建立一个电视网络，将直播流程广播给AA市的所有居民。

AA市的电视网络由加权平面无向图表示，其中广播站点作为顶点，站点之间的电缆作为边。 AtCoder办公室位于与坐标为$(x_1, y_1) = (0, 0)$的广播站点1相同的建筑物中。您可以针对每根电缆打开/关闭电源，从第1个站点只使用打开电源的电缆可以进行广播的辐射。您可以调整每个站点的广播无线电波的输出强度，直播传送的区域取决于输出强度。

请构建一个能够将实时直播传送给所有居民的电视网络，同时减少使用传输电缆和广播无线电波的成本。

问题陈述

给定一个具有N个顶点和M条边的加权平面无向图G。顶点i的坐标为$(x_i, y_i)$。第j条边连接顶点$u_j$和$v_j$，其权重为$w_j$。设$D_j=\\mathrm{round}\\left(\\sqrt{(x_{u_j}-x_{v_j})^2+(y_{u_j}-y_{v_j})^2}\\right)$为顶点$u_j$和$v_j$之间的舍入欧几里得距离。那么，权重$w_j$满足$100D_j\\le w_j\\le 2500D_j$。您还知道居民的K个坐标，第k个居民的坐标为$(a_k, b_k)$。

您应该为每条边设置电源的开/关以及每个顶点$i=1,2,\\cdots,N$的输出强度整数$P_i\\ (0\\le P_i\\le 5000)$。令$E'$为电源为开的边的集合。从G中移除不包含在$E'$中的边得到子图$G'$，并令$V'$为从顶点1在$G'$中可达的顶点集合。对于$V'$中的每个$i$，生活在以坐标$(x_i, y_i)$为中心、半径为$P_i$的圆形区域内（包括圆周）的居民将能够观看到实时直播。

将边$j$的电源设置为开会产生成本$w_j$。此外，将顶点$i$的输出强度设置为$P_i$会产生成本$P_i^2$。您可以为$i\\notin V'$设置$P_i$为正值，但这不会扩展广播覆盖区域并产生不必要的成本。请构建一个能够将实时直播传送给所有居民的电视网络，同时尽量减少成本总和$S=\\sum_{i=1}^N{P_i^2}+\\sum_{j\\in E'} w_j$。

评分

设$n$为直播覆盖范围内的居民数量。则你将获得以下分数。

• 如果$n\\lt K$，得分为$\\mathrm{round}(10^6 \\times (n+1)/K)$。
• 如果$n=K$，得分为$\\mathrm{round}(10^6\\times(1+10^8/(S+10^7)))$。

注意$S$可能不适应32位整数。

共有300个测试用例，提交得分为所有测试用例的总分。种子为0的输入是手动创建的，不包含在测试用例中。如果您的提交产生非法输出或在某些测试用例中超出时间限制，则提交将被判定为WA