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 Input consists of multiple test cases, each of them as described below. The first line of the input contains the number of test cases. There is a blank line before each dataset. The input for each dataset 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 for each dataset is one single line, which contains an integer with the sum of the cooking times for all the dishes in the competition. Print a blank line between datasets. Sample Input 2 45 9 025 033 1 1 20 1 4 10 2 1 25 2 4 30 302 3 2 10 3 3 12
2/2 33 9 003 012 021 101 117 129 203 217 225 Sample Output 40 8