{"raw_statement":[{"iden":"background","content":"安宁顷刻今将逝，末日黑云伺隙来。宿命无情何所惧？越其止境冀花开。\n\n为了执行毁灭世界的疯狂计划，一位占用了已死之人躯壳的神秘男子在这颗蓝色的星球上创造出了无数末日塔。这些末日塔会散发出浓密的以太射线，对末日塔附近的几乎所有生物进行精神控制，只有受到特殊加护的人才能免受以太射线控制。\n\n一些受到加护的义勇队对这些末日塔进行了调查，其结果显示：这些末日塔组成了复杂的以太传输网络，持续不断地从大地中吸收以太，并将以太传输到位于帝国的中枢塔。\n\n一队持有特殊加护的英雄决定闯入其中一些末日塔，以期彻底调查并尝试破坏这些末日塔。英雄们破坏掉进入的末日塔后，以太传输网络就会受到影响，因此大家希望选择一些末日塔，将其破坏后能使得网络的最大传输容量降到最低。\n\n作为勇闯末日塔小队的先锋，你再次阅读了小队目前所掌握的所有信息。这次大胆的行动计划最终能否拯救这个世界，眼下恐怕谁都无法事先料定。但为了这颗星球的未来，我们只能放手一搏。"},{"iden":"statement","content":"星球的表面是一个中心位于 $(0, 0, 0)$，半径为 $R$ 的完美球面。星球表面上共有 $N$ 座末日塔，这些令人毛骨悚然的塔构成了以太传输网络的所有节点。\n\n- 末日塔的高度远小于星球半径，因此我们认为第 $i (1 \\le i \\le N)$ 座塔是球面上的一个点 $\\left(x_i, y_i, z_i\\right)$。第 $i$ 座塔的以太传输效率为 $q_i$。\n- 保证 $N$ 座末日塔的位置两两不同。在这 $N$ 座末日塔中，$s$ 号塔是以太吸收点，$t$ 号塔是位于帝国的中枢塔；这两座塔的以太浓度显著高于其它的末日塔，因此只能闯入这两座塔之外的末日塔。\n\n$N$ 座末日塔之间共有 $M$ 条传输通道。第 $j (1 \\le j \\le M)$ 条传输通道连接 $u_j, v_j$ 两座末日塔，让它们可以互相传输以太。\n\n- 传输通道是双向的，但单位时间内以太的流向必须是单向的。\n- 为了节省不必要的成本，传输通道的两端不会连接相同的塔，也不会有两条传输通道连接相同的末日塔对。\n- 为了降低传输距离，第 $i$ 条传输通道沿着 $u_j$ 和 $v_j$ 所在的大圆的劣弧铺设，故其**长度** $r_j$ 为两座末日塔在星球表面的球面距离。为了避免传输通道的互相干扰，**对于任意一条传输通道所对应的劣弧，其他传输通道所对应的劣弧只会在该劣弧的两端点上与该劣弧相交**。保证由同一条传输通道相连的两座末日塔的位置不是对跖点关系。\n  - 如果不知道大圆、劣弧、球面距离和对跖点是什么，可以参考题面最后的提示部分。\n\n受到传输效率和通道长度的影响，每条传输通道有各自传输以太的容量上限。\n\n- 具体而言，每个单位时间内，第 $j$ 条传输通道的**容量上限**为 $\\frac{Kq_{u_j} q_{v_j}}{r_j^2}$，其中 $K$ 是给定的常数，$q_{u_j}, q_{v_j}$ 为该传输通道两端的塔的传输效率，$r_j$ 为这条传输通道的长度。\n\n整张以太传输网络需要将 $s$ 号塔吸收的以太沿着传输通道传输到 $t$ 号塔，并使得单位时间内的以太传输量最大。为此，传输网络会自动确定一个以太传输方案，在满足所有传输通道容量上限的前提下，最大化这一传输量。\n\n- 换句话说，如果将末日塔看作图上的点，传输通道看作边，而传输通道的容量上限对应每条边的容量，那么以太的传输方案应该恰好为 $s$ 到 $t$ 的最大流。\n\n虽然没有任何人能保证闯入末日塔之后就一定能将其破坏，但作为勇闯末日塔小队的先锋，你还是想在出发之前计算一下，如果成功破坏了所有将要闯入的末日塔，传输网络单位时间的最大传输量将会降至多少。\n\n- 如果成功破坏了选择的末日塔，与其相连的所有传输通道的容量都将降至 $0$，其余传输通道容量不发生变化；此时传输网络会自动调节至一个在新的网络中传输量最大的新方案。\n- 在最理想的情况下，小队将有机会调查并破坏 $L$ 座末日塔。因此，需要事先选择 $L$ 座末日塔（均不能是 $s$ 或 $t$），使得当这 $L$ 座末日塔都被成功破坏时，传输网络的新的传输方案的以太传输量尽可能地小。"},{"iden":"input","content":"输入的第一行包括五个正整数 $N, M, L, s, t$（$3\\le N\\le 500$，$2\\le M\\le \\frac{N(N-1)}{2}$，$1\\le L\\le \\min\\{8,N-2\\}$，$1\\le s, t\\le N$），分别表示该传输网络包含的末日塔数量，传输通道数量，有机会闯入的末日塔数量，最主要的以太吸收塔的编号和中枢塔的编号。\n\n输入的第二行包括两个实数 $R, K$（$1\\le R\\le 10^3$，$1\\le K\\le 10^3$），分别表示星球的半径和计算以太容量时用到的常数。\n\n接下来 $N$ 行，每行三个实数 $a_i, b_i, q_i$（$0\\le a_i\\le 1$，$0\\le b_i< 2$，$1\\le q_i \\le 10^3$），描述第 $i$ 座末日塔的信息，其中 $q_i$ 表示第 $i$ 座末日塔的传输能力， $a_i$ 和 $b_i$ 共同描述末日塔的位置：令 $\\theta_i = \\pi a_i$，$\\varphi_i = \\pi b_i$（如果你习惯使用角度制而不是弧度制，可以将 $\\pi$ 改为 $180^\\circ$），则 $\\left(x_i, y_i, z_i\\right) = \\left(R \\sin\\theta_i \\cos\\varphi_i, R\\sin\\theta_i \\sin\\varphi_i, R\\cos\\theta_i\\right)$。保证末日塔的位置各不相同。\n\n最后 $M$ 行，每行两个正整数 $u_i, v_i$（$1\\le u_i, v_i\\le N$），表示一条传输通道连接的两座末日塔的编号。保证同一条传输通道连接的两座末日塔不相同且不互为对跖点，没有两条传输通道连接的是相同的末日塔对，且传输网络是连通的。\n\n保证输入的所有实数保留到小数点后第 $4$ 位。"},{"iden":"output","content":"输出一个实数，表示如果成功破坏了将要闯入的末日塔，新的传输网络单位时间的最大传输量。当你的输出与标准输出的相对误差或绝对误差不超过 $10^{-6}$ 时，我们认为你的输出是正确的。"},{"iden":"note","content":"### 样例 \\#1 解释\n\n以太传输网络如下图所示。图中蓝色球面即为星球表面；紫色点为各末日塔，其中 $P_i$ 对应输入的第 $i$ 座末日塔；黄色的线表示各传输通道。\n\n![样例 1 示意图](https://cdn.luogu.com.cn/upload/image_hosting/4bynt5dl.png)\n\n原来的传输网络单位时间最大传输量为 $188/\\pi^2$。破坏第 $2$ 个末日塔或第 $5$ 个末日塔都能使新的传输网络单位时间的最大传输量降至 $80/\\pi^2$，而破坏第 $3$ 个末日塔或第 $4$ 个末日塔只能使新的传输网络单位时间的最大传输量降至 $94/\\pi^2$，所以应该选择第 $2$ 个或第 $5$ 个末日塔尝试破坏。"}],"translated_statement":null,"sample_group":[["6 11 1 1 6\n1.0000 1.0000\n1.0000 0.0000 10.0000\n0.7500 0.2500 6.0000\n0.5000 0.0000 1.0000\n0.5000 0.5000 1.0000\n0.2500 0.2500 6.0000\n0.0000 0.0000 10.0000\n1 2\n1 3\n1 4\n2 3\n2 4\n3 4\n3 5\n3 6\n4 5\n4 6\n5 6\n","8.105694691387022\n"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}