Welcome to ZOJ
Select Problem
ZOJ Problem Set - 3474

Time Limit: 2 Seconds      Memory Limit: 65536 KB

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:

  1. Axe Kick:consume P1 energe power, get 3 points
  2. Back-Whirling Kick: consume P2 energe power, get 2 points
  3. Turning Kick: consum P3 energe power, get 1 points
P1, P2, P3 depends on the opponent and will be given in the input. For example, if the opponent is taller than Alice, then Axe Kick may consume more energe, but for a shorter opponent, it will be easier to use Axe Kick,thus consuming less energe.

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".

Sample Input

2 100
40 40 40 100
20 70 10 100
1 10
40 40 40 100

Sample Output



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
Submit    Status