在该大学的一个巨大操场上将举行一场程序设计竞赛。整个操场将被划分为 $N$ 个区域，并且有 $M$ 条有向通道连接这些区域。第 $i$ 条通道从第 $u_i$ 个区域通往第 $v_i$ 个区域。你的任务是解决午餐问题。根据安排，第 $i$ 个区域有 $s_i$ 名参赛者。受限于桌子的大小，第 $i$ 个区域会放置 $b_i$ 份午餐（包括面包、香肠和牛奶）。因此，一些参赛者需要移动到另一个区域去吃午餐。然而，由于操场是临时布置的，通道上会有很多电线。

对于第 $i$ 条通道，电线起初是稳固的，第一个通过它的参赛者不会弄断电线。然而，在此之后，当有人通过第 $i$ 条通道时，有 $p_i$ 的概率会触碰到电线并影响整个网络。此外，为了保护这些电线，允许通过第 $i$ 条通道的参赛者人数不能超过 $c_i$。

现在你需要找到一种方案，让所有参赛者都能拿到午餐，并使网络崩溃的概率最小。

输入格式

输入的第一行包含一个整数 $t$，表示测试数据的组数。接下来是 $t$ 组测试数据。

对于每组测试数据：

第一行包含两个整数 $N$（$N \le 100$）和 $M$（$M \le 5000$）。

接下来的 $N$ 行，每行包含两个整数 $s_i$ 和 $b_i$（$s_i, b_i \le 200$）。

接下来的 $M$ 行，每行包含三个整数 $u_i$、$v_i$ 和 $c_i$（$c_i \le 100$）以及一个浮点数 $p_i$（$0 < p_i < 1$）。

保证至少存在一种方案能让每位参赛者都拿到午餐。

输出格式

对于每组测试数据，输出网络崩溃的最小概率。结果保留两位小数。

样例

输入样例 1

1
4 4
2 0
0 3
3 0
0 3
1 2 5 0.5
3 2 5 0.5
1 4 5 0.5
3 4 5 0.5

输出样例 1

0.50