The PDF version of this problem can be downloaded here.
Tomato the Great will held a party at the night of Pizza Festival. Many friends of him will come to the party, so he has to prepare a huge wave of pizza! There are n pizza stores on the street, and each of them sells two kinds of pizzas. There are totally n kinds of pizzas which are sold on the street, and each kind of pizza is sold in exactly two pizza stores. Tomato the Great would like to collect at least one of each kind for the party.
However, the pizza stores also held a special event for Pizza Festival, called Absolutely Cool Mystery { Invisible Content Pizza Container (ACM-ICPC). During the festival, one will not know in advance the taste of the pizza he is going to buy. That is, one will get a pizza in either of the two kinds sold in this store, but will not be sure about which kind of pizza exactly.
Tomato the Great knows the event, and he also know the number of pizzas of each kind sold in each store. Assume that all the pizzas are already made, and no more pizza will be produced. What is the minimum number of pizzas that he has to buy, to ensure that he can have at least one pizza of each kind? Note that he can know taste of these pizzas only after buying all pizza.
The first line of the input le contains an integer T (1 ≤ T ≤ 100) indicating the number of test cases.
Each test case starts with a line consisting of one integer n (2 ≤ n ≤ 1000). The following n lines describes the n pizza stores. The i-th line contains four integers, ai,
xi, bi, and yi (1 ≤ ai, bi ≤ 1000, 1 ≤ xi, yi ≤ n), indicating that the i-th pizza store has ai boxes of Pizza xi and bi boxes of Pizza yi.
For each test case please output an integer in one line, denoting the minimum number of pizza that Tomato the Great has to buy.
1 2 1 1 1 2 1 1 1 2
2
Migrated from old NTUJ.
dreamoon
| No. | Testdata Range | Score |
|---|