Data security has become a very important and difficult issue. If not handled properly, the consequences can be severe.

The military has the highest demand for security. To cope with satellites flying overhead, military bases are generally built underground.

The military base of country K is structured as follows: there are $n_1$ entrances/exits arranged in two rows on the surface. Internally, there are many cavities that are disconnected from each other except for the shared entrances/exits. Each cavity has exactly two entrances/exits, and these two entrances/exits are not in the same row. For convenience, the entrances/exits in the two rows are numbered $1, 3, 5, \dots$ and $2, 4, 6, \dots$ respectively, with the maximum number being $n_1$.

We have a highly capable special forces unit. If we send a team to a specific entrance/exit of the K country base, all cavities directly connected to this entrance/exit can be explored, but only these cavities can be explored by this team. We have enough special forces teams at your disposal, and you must use them to investigate all the cavities within the K country base.

Your base is not too close to the K country base. You are given a map of the surrounding area, represented as $n$ checkpoints and $m$ roads connecting these points. Points $1$ to $n_1$ are the entrances/exits of the K country base, and point $n$ is the starting point of your troops. For each road, there is a travel time $t$ and a safety coefficient $s$. Since the intelligence department has only evaluated the safety coefficients for one-way roads, these roads are one-way only, and there are no cycles.

A special forces team starts from your base, travels along a path, and reaches a K country base entrance/exit. The risk of this team is defined as the ratio of the total time to the sum of the safety coefficients of all roads passed along this path. The total risk of the entire operation is defined as the sum of the risks of all the teams you send. You need to explore the entire K country base while minimizing this total value.

Input

The first line contains two positive integers $n$ and $m$ ($4 \le n \le 700$, $m \le 100\,000$), representing the number of checkpoints and roads in the entire area map.

The next $m$ lines each contain four positive integers $a, b, t, s$ ($a, b \le n$, $1 \le t, s \le 10$), representing a road from $a$ to $b$ with travel time $t$ and safety coefficient $s$.

The next line contains two positive integers $m_1$ and $n_1$ ($m_1 \le 40\,000$, $n_1 < \min\{n, 161\}$), where $m_1$ is the number of cavities in the K country base, and $n_1$ is the number of entrances/exits.

The next $m_1$ lines each contain two positive integers $u, v$ ($u, v \le n_1$, $u$ is odd, $v$ is even), representing the two entrances/exits of each cavity.

Output

A single line containing the minimum total risk, rounded to one decimal place. If the task is impossible, output "-1".

Examples

Input 1

5 5
5 1 10 1
5 1 10 1
5 2 9 1
5 3 7 1
5 4 8 1
4 4
1 2
1 4
3 2
3 4

Output 1

17.0

Subtasks

For 30% of the data, $n \le 30$. For 60% of the data, $n \le 300$. Additionally, for 40% of the data, $n_1 \le 20$.