# Coding Contest

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

## Description

A coding contest will be held in this university, in a huge playground. The whole playground would be divided into N blocks, and there would be M directed paths linking these blocks. The i-th path goes from the $u_i$-th block to the $v_i$-th block. Your task is to solve the lunch issue. According to the arrangement, there are $s_i$ competitors in the i-th block. Limited to the size of table, $b_i$ bags of lunch including breads, sausages and milk would be put in the i-th block. As a result, some competitors need to move to another block to access lunch. However, the playground is temporary, as a result there would be so many wires on the path.
For the i-th path, the wires have been stabilized at first and the first competitor who walker through it would not break the wires. Since then, however, when a person go through the i - th path, there is a chance of $p_i$ to touch
the wires and affect the whole networks. Moreover, to protect these wires, no more than $c_i$ competitors are allowed to walk through the i-th path.
Now you need to find a way for all competitors to get their lunch, and minimize the possibility of network crashing.

## Input

The first line of input contains an integer t which is the number of test cases. Then t test cases follow.
For each test case, the first line consists of two integers N (N ≤ 100) and M (M ≤ 5000). Each of the next N lines contains two integers si and $b_i$ ($s_i$ , $b_i$ ≤ 200).
Each of the next M lines contains three integers $u_i$ , $v_i$ and $c_i(c_i$ ≤ 100) and a float-point number $p_i$(0 < $p_i$ < 1).
It is guaranteed that there is at least one way to let every competitor has lunch.

## Output

For each turn of each case, output the minimum possibility that the networks would break down. Round it to 2 digits.

## Sample Input

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

## Sample Output

0.50

jiangzijing2015

## Source

2016ACM/ICPC亚洲区青岛站-重现赛（感谢中国石油大学）