Background

Xiao S is a student at a famous university in the capital city. On the night after his final exams, Xiao S went out alone to treat himself after days of exhausting revision. Unexpectedly, it started raining while he was having dinner. Although the capital has a warm-temperate, semi-humid, semi-arid monsoon climate, it is quite rare for a significant amount of rain (not snow) to fall suddenly in January.

Xiao S checked the weather forecast and found that the rain might get heavier, so he planned to take a taxi back to his dormitory. As luck would have it, just after he ordered a taxi, his phone ran out of battery and shut down. Searching through his bag and pockets, Xiao S could not find any change for the taxi or a charging cable to revive his phone. The only comfort for Xiao S was the rabbit-shaped milk candy he had thoughtfully packed in his bag—this snack from the mysterious Magic City is his favorite. With no other choice, Xiao S decided to brave the rain and walk back to his dormitory on foot.

Description

The transportation network from the restaurant to the dormitory can be abstracted as an undirected connected graph with $N$ nodes and $M$ edges. There are no multiple edges or self-loops, and both nodes and edges are numbered with natural numbers starting from 1. The restaurant is at node $x$, and the dormitory is at node $y$. When Xiao S travels, it takes exactly $l_i$ minutes to traverse the $i$-th edge. Although Xiao S could take the shortest path back to the dormitory, he prefers to minimize the total amount of rain he is exposed to. Due to factors like buildings on both sides of the road, the amount of rain exposed to on different roads may vary; furthermore, under different weather conditions, the amount of rain exposed to on the same road may also differ. Specifically, under the current weather conditions, Xiao S is exposed to $a_i$ units of rain per minute when traversing the $i$-th edge; however, if the rain gets heavier, he will be exposed to $b_i$ units of rain per minute when traversing the $i$-th edge.

Since Xiao S's phone is dead, he cannot know exactly when the rain will get heavier. However, he glanced at the sky and calculated $K$ possible time points $T_1, T_2, \dots, T_K$ when the rain might intensify, where the probability that the rain intensifies exactly $T_i$ minutes after he departs from the restaurant is $p_i$. Xiao S wants to find a strategy to return to the dormitory that minimizes the expected total amount of rain he is exposed to under this given distribution. Specifically, this strategy consists of a set of decisions, where each decision determines which edge Xiao S should take next based on the current time, whether the rain has already intensified, and his current location. Since Xiao S is in a hurry to return to the dormitory, we stipulate that he will not stop at any node other than the destination (dormitory $y$) or on any edge, and he will not turn back while traversing an edge.

Input

Read the data from standard input.

The first line contains five positive integers $N, M, K, x, y$, representing the number of nodes, the number of edges, the number of time points when the rain might intensify, the location of the restaurant, and the location of the dormitory, respectively. It is guaranteed that $2 \le N \le 1000, 1 \le M \le 4000, 1 \le K \le 1000, 1 \le x, y \le N$, and $x \ne y$.

The next $M$ lines each contain five positive integers $u_i, v_i, l_i, a_i, b_i$, representing the two endpoints of the $i$-th edge, the time required to traverse the $i$-th edge, the rain exposure per minute when the rain is light, and the rain exposure per minute when the rain is heavy, respectively. It is guaranteed that $1 \le u_i, v_i \le N, 1 \le l_i \le 20, 1 \le a_i \le b_i \le 100,000$, and the undirected graph contains no multiple edges or self-loops.

The last $K$ lines each contain two positive integers $T_i, w_i$. $T_i$ is the $i$-th time point when the rain might intensify, and the corresponding probability is $p_i = w_i / \sum_{j=1}^K w_j$. It is guaranteed that $1 \le T_1 < T_2 < \dots < T_K \le 10000$ and $1 \le w_i \le 1000$.

Output

Output to standard output.

Output a positive real number representing the minimum expected total rain exposure under the optimal strategy. Your output is considered correct if the relative or absolute error is within $10^{-6}$.

Examples

Input 1

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

Output 1

13.000000000000000000

Note 1

Xiao S believes there is a $1/2$ probability that the rain intensifies 3 minutes after his departure, and a $1/2$ probability that it intensifies 6 minutes after his departure.

If it is known that the rain will definitely intensify 3 minutes after departure, the optimal strategy is: first take edge $(1, 3)$ to reach node 3, during which the rain intensifies, exposing him to 7 units of rain; then take edge $(3, 4)$ to return to the dormitory, exposing him to 9 units of rain. The total rain exposure is 16.

If it is known that the rain will definitely intensify 6 minutes after departure, the optimal strategy is: first take edge $(1, 2)$ to reach node 2, exposing him to 3 units of rain; then take edge $(2, 4)$ to return to the dormitory, exposing him to 6 units of rain. The total rain exposure is 9. This is also the fastest path.

Based on the distribution, the optimal strategy is: first take edge $(1, 2)$ to reach node 2; at this point, it is exactly 3 minutes after departure. If the rain intensifies now, take edges $(2, 3)$ and $(3, 4)$ to return to the dormitory, resulting in $3 \times 1 + 1 \times 5 + 3 \times 3 = 17$ units of rain. Otherwise, it can be inferred that the rain will intensify 6 minutes after departure, so he can take edge $(2, 4)$ to return to the dormitory, resulting in $3 \times 1 + 2 \times 3 = 9$ units of rain. The expected rain exposure is $17 \times \frac{1}{2} + 9 \times \frac{1}{2} = 13$.

Examples 2-4

See the provided files ex_2.in/ex_2.ans, ex_3.in/ex_3.ans, and ex_4.in/ex_4.ans.

Subtasks

For 100% of the data, it is guaranteed that: - $2 \le N \le 1000, 1 \le M \le 4000, 1 \le K \le 1000$; - $1 \le x, y \le N$, and $x \ne y$; - The undirected graph has no multiple edges or self-loops and is connected; - For the $i$-th edge, $1 \le u_i, v_i \le N, 1 \le l_i \le 20, 1 \le a_i \le b_i \le 100,000$; - For the given time points, $1 \le T_1 < T_2 < \dots < T_K \le 10000$ and $\forall 1 \le i \le K, 1 \le w_i \le 1000$.

There are 5 subtasks. You must pass all test cases in a subtask to receive the corresponding points.

Note

If you are unfamiliar with conditional probability, here are some hints that may help:

We denote $P(A|B)$ as the conditional probability of event $A$ occurring given that event $B$ has occurred. If $P(B) \neq 0$, this can be calculated as:

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

where $P(AB)$ is the probability that both $A$ and $B$ occur, and $P(B)$ is the probability of event $B$. In this problem, the rain intensifying at each time point can be considered mutually exclusive events that form a partition of the sample space $\Omega$. Let $A_i$ be the event that the rain intensifies exactly $T_i$ minutes after departure. Then:

• All $A_i$ form a partition of $\Omega$, i.e., $\cup_{i=1}^K A_i = \Omega$, with $P(\Omega) = 1$.
• $A_i$ are mutually exclusive, i.e., $\forall i \neq j, A_i \cap A_j = \varnothing$, with $P(A_i A_j) = 0$.

From these properties, given that the rain did not intensify exactly $T_i$ minutes after departure (event $\bar{A_i}$), the conditional probability that the rain intensifies at $T_j$ ($j \neq i$) is:

$$ 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} $$

Furthermore, for three events $A_i, A_{j_1}, A_{j_2}$ (where $i, j_1, j_2$ are distinct), it can be proven that:

$$ \frac{P\left(A_{j_1}|\bar{A_i}\right)}{P\left(A_{j_2}|\bar{A_i}\right)} = \frac{w_{j_1}}{w_{j_2}}=\frac{P\left(A_{j_1}\right)}{P\left(A_{j_2}\right)} $$

That is, the ratio of probabilities of two events in a partition is independent of whether other events in the partition have occurred. Although the information known in this problem is whether a prefix of events (i.e., $A_1 \cup A_2 \cup \dots \cup A_i$) has occurred, this property still holds.