ACM Coalition

Time limit1sMemory limit128 MB

Summary

Pick parties whose seats cover the shortage and grant one demand each so ACM's remaining board votes are maximal.

Level: Medium7 of 10
Topics: Dynamic programming
Solved: No attempts yet

Problem

No party won a majority in the recent parliament election, so filling the Management Board takes a coalition. The board has one speaker, two deputy speakers and six secretaries. Voting on the board is weighted: the speaker casts 25 votes, each deputy speaker casts 8 votes, and each secretary casts 1 vote.

The ACM party wants to lead the coalition, but it is $m$ seats short of a majority. It knows how many seats every other party holds. In return for joining the coalition, a party demands a share of the board as a triplet $(a, b, c)$ , where $a$ , $b$ and $c$ are the numbers of speakers, deputy speakers and secretaries it expects to be chosen from its own ranks. If the party BDN demands $(1, 1, 2)$ , then the speaker, one deputy speaker and two secretaries have to come from BDN. A party may state several demands, and then it joins the coalition as soon as one of them is met.

The seats of the parties that join have to add up to at least $m$ , which is what covers the shortage of ACM. Every board position left over after the demands are filled goes to ACM. Maximize the total number of votes ACM holds on the board.

Input

The input holds several test cases.

Each test case starts with a line containing two integers $n$ and $m$ . Here $n$ is the number of parties other than ACM ( $n \le 50$ ) and $m$ is the number of seats ACM is short. The next $n$ lines describe one party each. Such a line starts with the number of seats that party holds, then a colon, a space, and the list of its demands. A demand has the form $(a, b, c)$ with $0 \le a \le 1$ , $0 \le b \le 2$ and $0 \le c \le 6$ . Demands are separated by or, and the list ends with a semicolon.

The last line of the input is 0 0. Every test case admits at least one coalition that covers the $m$ seats.

Output

For each test case, print one line with three integers: the numbers of speakers, deputy speakers and secretaries that ACM gets in a coalition maximizing its votes.

One speaker outweighs two deputy speakers plus six secretaries, and one deputy speaker outweighs six secretaries, so the vote-maximizing share is unique.

Examples2

Example 1

Input

3 4
1: (0,0,0);
2: (1,2,0);
3: (1,0,5) or (1,2,0) or (0,2,6);
1 0
1: (1,1,1);
1 1
1: (1,1,1);
4 6
6: (1,0,0) or (1,2,6);
2: (0,2,0);
2: (0,0,3);
2: (0,0,3);
0 0

Expected output

Example 2

Input

3 9
3: (1,0,0);
3: (0,1,0);
3: (0,0,2);
0 0

Expected output

0 1 4