Dangerous Situation

Long long time ago, there was one island with several village. People living on the island choose one leader as the CHIEF per four years. This time, a leader was picked to continue in office for another term but not all the people support him, especially the owner of the supermarkets and supplier in villages because he has promised to build roads between each village but no roads seemed to be under constructed.
To get the support of the owners, the chief was thinking about building roads. But the situation was more dangerous because the chief was so mean that he decide to build roads only with the most reasonable price and he want to build as less roads as possible even if no roads can be built between two villages . Engineer Ei come up with different plan of road construction with different price Pi and capability Ci. Only the the road with the highest Ci/Pi rate will be picked as the final plan.
On the exciting day, the chief will gather all the plan the engineers come up with and decide whether each of them is packed or not. The chief will check the list on which the plans are listed with the order based on the time when the plan was submitted to the chief. A road building plan was changed only if there is a better Ci/Pi connecting the same points.
However, not all the one will satisfy. If the one of the supermarkets can’t get enough goods from the supplier, or the suppliers cannot sell his goods to any of the supermarket, the rich owners will gather their wealth and impeach the chief, and the chief will surely step down the office as his enemy was so powerful. Your job is to find out whether the chief can survive this dangerous situation.

The input will have several test cases. First line is t (t<=10) integer t indicating the number of test cases. Then comes two integers n (n<=200) and m which indicate the number of villages and the number of supermarket (the number of supplier is n-m). Next m line is 2 number in line i where Si and Di (Di<=1000) indicate the supermarket located in the ith village have a demand of Di (the else ones are suppliers). The next line has a number p (p<=5000) indicating the number of road plans. Then p lines followed with four integers per line, s, e, c (c<=1000), v (v<=1000) indicating the start, the end, the capability, the price of the road engineer come up with.

The output will contain one line with “Yes” or “No” indicating whether the chief can survive the dangerous situation.

1
4 2
1 100
2 100
3
1 2 200 40
1 3 200 40
2 4 200 30

Yes

2010 ACM-ICPC Multi-University Training Contest（6）——Host by BIT