[Sdoi2011]保密

现在，保密成为一个非常重要且困难的问题。如果保密工作没有做好，后果可能十分严重。为了应对天上飞行的卫星，军事基地通常会建造在地下。

某 $K$ 国的军事基地由地面上的两排大型天井作为出入口，共有 $n_1$ 个出入口。基地内部有许多空腔，除共享出入口外，空腔之间互不连通。每个空腔恰好有两个出入口，并且这两个出入口不在同一排。为方便起见，两排出入口分别编号为 $1,3,5,\ldots$ 和 $2,4,6,\ldots$ ，最大编号为 $n_1$ 。

现在有足够多的特种部队可以调遣。派出一支特种部队到达 $K$ 国基地的某个出入口后，与该出入口直接相连的所有空腔都可以被探索，除此之外的空腔无法被这支部队探索。你必须派出若干支部队，调查完基地内的所有空腔。

你的基地与 $K$ 国基地之间的地图包含 $n$ 个检查点和 $m$ 条单向道路，其中检查点 $1$ 到检查点 $n_1$ 是 $K$ 国基地的出入口，检查点 $n$ 是特种部队的出发点。由于情报部门只评估了单向道路的安全系数，因此所有道路均只能单向通行，且道路网络中不存在环。

每条道路有通行时间 $t$ 和安全系数 $s$ 。一支特种部队从检查点 $n$ 出发，沿某条路径到达一个基地出入口。该部队的危险性定义为这条路径的总通行时间与经过的所有道路的安全系数之和的比值。整个行动的危险性为所有派出部队的危险性之和。

请在调查完所有空腔的前提下，使整个行动的危险性最小。如果任务无法完成，请输出 $-1$ 。

输入格式

第一行包含两个正整数 $n$ 和 $m$ ，表示地图中的检查点数和道路数。

接下来 $m$ 行，每行包含四个正整数 $a$ 、 $b$ 、 $t$ 和 $s$ ，表示存在一条从检查点 $a$ 到检查点 $b$ 的单向道路，其通行时间为 $t$ ，安全系数为 $s$ 。

接下来一行包含两个正整数 $m_1$ 和 $n_1$ ，其中 $m_1$ 表示基地内空腔的数量， $n_1$ 表示基地出入口的数量。

接下来 $m_1$ 行，每行包含两个正整数 $u$ 和 $v$ ，表示一个空腔的两个出入口。其中， $u$ 为奇数， $v$ 为偶数。

输出格式

输出一行，表示最小的行动危险性，保留一位小数。

如果任务无法完成，输出 -1。

样例输入

样例输出

17.0

数据范围

$4\le n\le 700$ ；
$m\le 10^5$ ；
$a,b\le n$ ；
$1\le t,s\le 10$ ；
$m_1\le 40000$ ；
$n_1<\min\{n,161\}$ ；
$u,v\le n_1$ ，且 $u$ 为奇数、 $v$ 为偶数。

来源与许可

本题为 SDOI 2011 试题「保密」，题面与测试数据整理自 BZOJ。

样例 1

输入

输出

17.0