56 - ZOJ Monthly, October 2006 - 1001
RPG (Role Play Games) is Vivid's favorite computer game type, such as Final Fantasy and Xian Jian Qi Xia Zhuan are both of this type. You may be even more familiar with it than Vivid is.
In these games, characters may have many attributes, e.g. physical force, attack ability, defence ability and so on. A lot of equipment types (weapon, armor, costume and so on) are also available in these games, and the equipments can alter (promotion or reduction) those character-attributes. E.g. Equipment with the attributes 10, 0, -10 means it will promote the first attribute of the character by 10, reduce the third attribute of the character by 10, and keep the second attribute unchanged.
In this problem, characters only have 3 attributes -- physical force, attack ability and defence ability. Lots of equipment types are available. You can choose at most one equipment from each type. Your goal is to make the lowest attribute as high as possible. If more than one choice exist, choose the one with higher value of the second lowest attribute. If there is still a tie, choose the one with higher highest attribute, you will be guaranteed that there is no tie then. For example, if one choice is 10, 20, 30 and the other one is 11, 11, 11, then the second will be chosen, for the lowest attribute of later is 11 while the lowest attribute of the former is 10. Another example, if one choice is 10, 20, 30 and another choice is 20, 10, 29, then the first will be chosen, for the lowest and the second lowest attributes of them are equal, and the highest attribute of the first is higher than the second.
The first line of the input is the total number of the test cases. Each test case begins will an integer T (the number of the equipment types, 1 <= T <= 16). Each block of equipment types will begins with an integer E (0 <= E <= 16), indicating the number of equipments of this type. Then E lines follows, each of them contains three integers A, B, C (all of them are in the range of [-100, 100]) indicating the effect to the character attributes (physical force, attack ability and defence ability).
Three integers should be printed in a single line for each test case, which are the final attribute values of physical force, attack ability and defence ability after equipment.Sample Input:
2 1 2 10 20 30 11 11 11 1 2 10 20 30 20 10 29Sample Output:
11 11 11 10 20 30
Author: JIN, Tianpeng