题目背景

小 S 是在幽燕之都的某著名大学上学的一名学生。考完期末考的当晚，小 S 独自一人出校犒劳一下多日来疲于复习的自己。没成想，在外面享用晚餐时，突然下起了雨。尽管幽燕之都是暖温带半湿润半干旱季风气候，但在一月突然下起有一定规模的雨（并且不是雪）实属罕见。

小 S 看了一下天气预报，发现雨可能会越下越大，便打算打车返回宿舍。屋漏偏逢连夜雨，当小 S 点完打车后，他的手机正好耗尽了所有电量，自动关机了。翻遍了书包口袋，小 S 也没有找到可以用来坐车的零钱，或是用来为手机续命的充电线。唯一能给小 S 一点安慰的，是他未雨绸缪在包里放的兔兔奶糖——源自神秘的魔力之都的这款零食是他的最爱。无奈之下，小 S 打算凭借他的两条双腿冒雨从餐馆赶回宿舍。

题目描述

从餐馆到宿舍的交通网络可以被抽象成一张有 $N$ 个点 $M$ 条边的无向连通图，图中没有重边也没有自环，点和边分别用从 $1$ 开始的自然数编号。餐馆在第 $x$ 号点，而宿舍在 $y$ 号点。小 S 赶路时，通过第 $i$ 条边恰好需要 $l_i$ 分钟。尽管小 S 可以直接沿着最短路赶回宿舍，但他更希望自己被淋到的雨越少越好。受到路两旁建筑物等多方面因素的影响，在不同路上淋到的雨量可能会有所不同；而在不同天气状况下，在同一条路上淋到的雨量也可能会有所不同。具体来说，在当前的天气状况下，小 S 通过第 $i$ 条边时每分钟会被淋到 $a_i$ 单位的雨；但是如果雨下大了，那么通过第 $i$ 条边时小 S 每分钟会被淋到 $b_i$ 单位的雨。

由于小 S 的手机没电关机了，他无法准确知道什么时候雨会开始下大，但是他瞅了一眼天空，掐指一算，给出了 $K$ 个雨可能会变大的时间点 $T_1, T_2, \cdots, T_K$，其中在他从餐馆出发后经过恰好 $T_i$ 分钟雨变大的概率是 $p_i$。小 S 希望，在这个给定的分布下，求出一个赶回宿舍的方案，使得他从出发到赶回宿舍为止被淋到的总雨量的期望最小。具体而言，这个方案由一组决策组成，每个决策根据当前时间、当前雨是否已经变大和小 S 所处的位置决定小 S 接下来应该沿着哪条边前进。由于小 S 急着赶回宿舍，我们规定，他不会在除了终点（即宿舍 $y$）以外的点或任意一条边上停留，并且也不会在沿着一条边走到中途时返回。

输入格式

从标准输入读入数据。

输入的第一行包含五个正整数 $N, M, K, x, y$，分别表示交通网络的点数、交通网络的边数、雨可能会变大的时间点数量、餐馆的位置及宿舍的位置。保证 $2\le N\le 1000, 1\le M\le 4000, 1\le K\le 1000, 1\le x, y\le N$ 且 $x\ne y$。

接下来输入 $M$ 行，其中第 $i$ 行包含五个正整数 $u_i, v_i, l_i, a_i, b_i$，分别表示第 $i$ 条边的两个端点、小 S 通过第 $i$ 条边所需时间、雨小时在第 $i$ 条路上每分钟会被淋到的雨量及雨大时在第 $i$ 条路上每分钟会被淋到的雨量。保证 $1\le u_i, v_i\le N, 1\le l_i\le 20, 1\le a_i\le b_i\le 100,000$，且输入的无向图不包含重边或自环。

最后输入 $K$ 行，其中第 $i$ 行包含两个正整数 $T_i, w_i$。其中，$T_i$ 表示第 $i$ 个雨可能变大的时刻，对应的发生概率 $p_i=w_i/\sum_{j=1}^K w_j$。保证 $1\le T_1 < T_2 < \cdots < T_K\le 10000$ 且 $1\le w_i \le 1000$。

输出格式

输出到标准输出。

输出一个正实数，表示在最优方案下，小 S 赶回宿舍过程中被淋到的总雨量。当你的输出和标准答案的相对误差或绝对误差在 $10^{-6}$ 以内时，我们认为你的输出是正确的。

样例

输入

4 5 2 1 4
1 2 3 1 4
2 4 2 3 8
1 3 4 1 4
3 4 3 3 3
2 3 1 3 5
3 1
6 1

输出

13.000000000000000000

解释

小 S 认为，有 $1/2$ 的概率雨在他出发后 $3$ 分钟时变大，另外有 $1/2$ 的概率是在出发后 $6$ 分钟时变大。

如果已知雨一定在出发后 $3$ 分钟时变大，那么赶回宿舍的最优方案为：先沿着边 $(1, 3)$ 到达点 $3$，由于途中雨变大，小 S 会被淋到 $7$ 单位的雨；接着沿着边 $(3, 4)$ 回到宿舍，被淋到 $9$ 单位的雨。路上小 S 总共被淋到 $16$ 单位的雨。

如果已知雨一定在出发后 $6$ 分钟时变大，那么赶回宿舍的最优方案为：先沿着边 $(1, 2)$ 到达点 $2$，被淋到 $3$ 单位的雨；接着沿着边 $(2, 4)$ 回到宿舍，被淋到 $6$ 单位的雨。路上小 S 总共被淋到 $9$ 单位的雨。这同时也是花费时间最少的方案。

根据小 S 推测的分布，最优的方案应该为：先沿着边 $(1, 2)$ 到达点 $2$；此时恰为从餐馆出发后 $3$ 分钟，如果雨此时变大，则沿着边 $(2, 3)$ 和 $(3, 4)$ 回到宿舍，这种情况下淋到的雨量为 $3\times 1+1\times 5+3\times 3=17$；否则，（根据所给分布）可推测雨一定是从餐馆出发后 $6$ 分钟时变大，则可以直接沿着 $(2, 4)$ 回到宿舍，这种情况下淋到的雨量为$3\times 1+2\times 3=9$。期望被淋到雨量为 $17\times \frac{1}{2}+9\times \frac{1}{2}=13$ 。

样例二

见下载目录下的 ex_2.in 与 ex_2.ans。

这个样例和第 $1$ 个子任务的性质相同。

样例三

见下载目录下的 ex_3.in 与 ex_3.ans。

这个样例和第 $3$ 个子任务的性质相同。

样例四

见下载目录下的 ex_4.in 与 ex_4.ans。

这个样例和第 $4$ 个子任务的性质相同。

子任务

对于 $100\%$ 的数据，保证：

• $2\le N\le 1000, 1\le M\le 4000, 1\le K\le 1000$；
• $1\le x, y\le N$，且 $x\ne y$；
• 输入的无向图无重边无自环，图是连通的；
• 对于第 $i$ 条边，$1\le u_i, v_i\le N, 1\le l_i\le 20, 1\le a_i \le b_i\le 100, 000$；
• 对于给出的时间点，$1\le T_1 < T_2<\cdots < T_K\le 10000$ 且 $\forall 1\le i\le K, 1\le w_i \le 1000$。

本题共有 5 个子任务，你需要通过一个子任务中的所有测试点才能获得该子任务的相应分数。下表为各子任务的数据规模及性质。

​

表格中的特殊性质 $S_1$ 表示：存在一种最优方案，满足赶回宿舍之前雨一定不变大。

提示

北京市紫荆区酒井蒜协提醒您：道路千万条，电量第一条；外出不充电，关机两行泪。

如果你不熟悉条件概率相关的内容，以下是一些对你做题可能有所帮助的提示。

我们记 $P(A|B)$ 表示在已知事件 $B$ 发生时事件 $A$ 发生的条件概率。如果事件 $B$ 发生的概率不为 $0$，这一条件概率可以使用以下公式进行计算：

$$ P(A|B)=\frac{P(AB)}{P(B)} $$

其中，$P(AB)$ 表示时间 $A$ 和 $B$ 同时发生的概率，而 $P(B)$ 表示事件 $B$ 发生的概率。在本题中，可以认为在每个时间点下雨是互斥事件，且它们组成了样本空间 $\Omega$。我们称这样的一组事件为样本空间的一个分割（或者划分）。记事件 $A_i$ 表示 $T=T_i$，即“从餐馆出发后经过恰好 $T_i$ 分钟雨变大”，则有：

• 所有的 $A_i$ 组成了样本空间 $\Omega$，即 $\cup_{i=1}^k A_i = \Omega$，对应概率$P\left(\cup_{i=1}^k A_i\right) = P(\Omega) = 1$；

• $A_i$ 之间两两互斥，即 $\forall 1\le i, j\le K, i\ne j, A_i \cap A_j=\varnothing$，对应概率 $P\left(A_i A_j\right) = P\left(\varnothing\right) = 0$。

由以上性质可以推出，在已知不是从餐馆出发后经过恰好 $T_i$ 分钟雨变大（对应事件 $\bar{A_i}$，即 $A_i$ 不发生）的条件下，出发后 $T_j (j\ne i)$ 分钟时下雨，也即事件 $A_j$ 发生的条件概率为：

$$ P\left(A_j | \bar{A_i}\right) = \frac{P\left(A_j \bar{A_i}\right)}{P\left(\bar{A_i}\right)}=\frac{P\left(A_j \right)}{P\left(\bar{A_i}\right)}=\frac{p_j}{\displaystyle\sum_{k\ne i} p_k}=\frac{w_j}{\displaystyle\sum_{k\ne i} w_k} $$

更进一步，对于本题中的三个事件 $A_i, A_{j_1}, A_{j_2}$（其中 $i, j_1, j_2$ 互不相同），可以证明：

$$ \frac{P\left(A_{j_1}|\bar{A_i}\right)}{P\left(A_{j_2}|\bar{A_i}\right)} = \frac{\dfrac{w_{j_1}}{\sum_{k\ne i} w_k}}{\dfrac{w_{j_2}}{\sum_{k\ne i} w_k}} = \frac{w_{j_1}}{w_{j_2}}=\frac{P\left(A_{j_1}\right)}{P\left(A_{j_2}\right)} $$

即在一组分割中，两个事件发生概率的比值与是否已知分割中其它事件发生与否无关。尽管在本题中，已知的信息是前缀的一系列事件（即 $A_1 \cup A_2\cup\cdots\cup A_i$）是否发生，但这一性质仍然成立。