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

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

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.

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.

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.

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.

提交代码