ZOJ Problem Set - 3474
Alice is very fond of Taekwondo and he is also a member of Taekwondo Association of Zhejiang University. One day, his friends decide to compare with him. Now Alice must face all of his friends'challange, that is to say, if there are T friends, then he will take T matchs in just one day! Of course Alice has limited energe power, so he must carefully arrange the order of the T matchs and take optional strategy to win all the matchs.
Here are the rules of taekwondo match. Player must use available kicks to hit available position of his opponent's body. Different kick gets different points. To simplify this problem, we assume that Alice will use only 3 kinds of kicks, as shown below:
If Alice wants to win a single match, he must get at least 7 points and guarantee that his enenge is above zero. After each match, Alice will have a chance to rest, and will recover R energe power, R also depends on different opponent. Alice's initial energe power is S , and after a rest, his energe power may be more than S, which is available. Remember that Alice can freely arrange the order of all the matches and he must win all the matches.
The first line of the input is a single integer m, which is the number of test cases. In each case, fisrt there are two integers T (T≤22) and S (S≤100), indicating that there are T friends to compare with Alice and Alice's initial energe power is S. the following T lines each contain 4 integers: Pi1, Pi2, Pi3, Ri, as described above. (0<=Pi1, Pi2, Pi3, Ri≤100)
For each case, you should output one line. If Alice can win all the matches, output the max energe power he can save at last. Otherwise,output "no".
2 2 100 40 40 40 100 20 70 10 100 1 10 40 40 40 100
In case 1, Alice should compare with the second person first, consume 50 energe power (2 Axe Kick and 1 Turning Kick), recover 100, then compare with the first person, consume 120 (2 Axe Kick and 1 Turning Kick), recover 100, thus the answer is 130.
Author: HUANG, Qiao
Contest: ZOJ Monthly, February 2011