SCITIES - Selfish Cities


Far, far away there is a world known as Selfishland because of the nature of its inhabitants. Hard times have forced the cities of Selfishland to exchange goods among each other. C1 cities are willing to sell some goods and the other C2 cities are willing to buy some goods (each city can either sell or buy goods, but not both). There would be no problem if not for the selfishness of the cities. Each selling city will sell its goods to one city only, and each buying city will buy goods from one city only.

Your goal is to connect the selfish cities in such a way that the amount of exchanged goods is maximalized.

Input

The first line contains a positive integer t<=1000 indicating the number of test cases. Each test case is an instance of the problem defined above. The first line of each test case is a pair of positive integers C1 and C2 (the number of cities wanting to sell their goods C1<=100 and the number of cities wanting to buy goods C2<=100). The lines that follow contain a sequence of (c1,c2,g) trios ending with three zeros. (c1,c2,g) means that the city c1 can offer the city c2 the amount of g<=100 goods.

Output

For each test case print the maximal amount of goods exchanged.

Example

Input:
3
3 2
1 1 10
2 1 19
2 2 11
3 2 1
0 0 0
4 4
1 1 6
1 2 6
2 1 8
2 3 9
2 4 8
3 2 8
4 3 7
0 0 0
3 2
1 1 10
2 1 21
2 2 11
3 2 1
0 0 0

Output:
21
29
22

hide comments
Luciano Ribeiro: 2016-11-05 15:57:09

Last edit: 2016-11-05 15:57:34
rahulpadhy: 2016-07-07 13:51:49

Its said that a particular city can either buy goods or sell goods, but not both.. But, in 1 of the test cases, its been mentioned : 1 1 6, which means that city 1 buys goods worth value 6 from city (or city 1 sells goods to city 1), which contradicts the questions statement itself as here, city 1 does both the tasks..

Rohit Singla: 2014-09-10 11:45:06

What is meant by this : 1 1 10??
Can the city sell goods to itself?

Amr Mesbah: 2012-11-23 20:32:34

@Ahmed Salem
100

Ahmed Salem [mrtempo]: 2012-10-31 21:21:04

What is the Output for this Input:
1
2 2
1 1 100
1 2 10
2 1 10

Is it 20 or 100 ?


Added by:Tomasz Niedzwiecki
Date:2005-01-22
Time limit:1.371s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All