D :: The Finest Chef

Time Limit: 5 Seconds    Memory Limit: 32768 KB

The World Finest Young Chef Competition welcomes young chefs from around the world. Making resources available for them to work is a very difficult job, because we cannot know, beforehand, what kind of equipment they are going to need. Each chef will be aiming to cook his best dish, but this can involve a stove, a fridge, a freezer, a microwave oven, etc. Each dish will only need one of these equipments once, for a limited period of time, but this period will vary, depending on the equipment used. For example, it is possible that one dish can be accomplished either using a fridge (using 30 minutes of the fridge's time) or a freezer (using only 5 minutes). Moreover, each equipment can only be used by one chef, for the duration of the competition, as after being used, it will need cleaning.

The aim is to find, for each chef, an equipment that will suit their dish, minimizing the sum of the cooking times of all of the dishes in competition.

Input

A positive integer P in a single line followed by a sequence of P competitions. The input begins with a line containing two positive integers to indicate the number of chefs in the competition, not greater than 250, and the number of facilities available to cook, not greater than 350. The next line contains a single integer, the number of lines to be read next. The following lines describe how long one chef's dish takes to cook in a specific facility, in the following way: one non-negative integer identifying the chef, one non-negative integer identifying the facility and a third positive integer for the cooking time. It is guarantied that there are enough facilities to cook all dishes.

Output

The output is one single line, which contains an integer with the sum of the cooking times for all the dishes in the competition.

Sample Input

2
4 5
9
0 2 5
0 3 3
1 1 20
1 4 10
2 1 25
2 4 30
3 0 2
3 2 10
3 3 12
3 3
9
0 0 3
0 1 2
0 2 1
1 0 1
1 1 7
1 2 9
2 0 3
2 1 7
2 2 5

Sample Output

40
8

Submit