ACM Coalition

Time Limit: 5 Seconds    Memory Limit: 65536 KB

In the recent parliament election, none of the parties have vast majority of seats, so there should be a coalition to select the members of the Management Board, which are one speaker, two deputy speakers and six secretaries. The board has a special voting system: the speaker has 25 votes, deputy speakers have 8 votes and each secretary has 1 vote.

ACM party decides to take a commanding role and shape the coalition, but they are m seats short to have a majority. They know the number of seats that every other party has taken. To participate in the coalition, each party demands its share from the Management Board in the form of a triplet (a, b, c) where a, b, and c are the number of speakers, deputy speakers, and secretaries that are expected to be selected from that party. For example, if the party BDN has a demand of (1, 1, 2), it expects that the speaker, one of the deputy speakers, and two of the secretaries are selected from BDN. A party may have multiple demands, meaning that the party accepts to participate in the coalition if one of its demands is satisfied.

Knowing the demands of all other parties, ACM wants to know how powerful it can be in Management Board. This means that ACM wants to maximize its number of votes while forming a coalition with other parties such that it overcomes its shortage of m seats.

Input

The input contains multiple test cases. Each test case starts with a line containing two integers n and m. The integer n is the number of line parties (n ≤ 50) and m is the number of seats ACM party needs. The next n lines contain other parties’ information, each beginning with number of seats the party has, followed by a colon, a space, and a list of demands for that party. The list of demands is in the form of triplets (a, b, c) where 0 ≤ a ≤ 1, 0 ≤ b ≤ 2, and 0 ≤ c ≤ 6. The triplets are separated by the string “ or ” and are terminated with a semicolon in the end (see the sample input).
The input is terminated with a line containing 0 0.

Output

For each test case, write a single line containing three integers, which represent speaker, deputy speaker and secretaries which ACM party can have in the coalition to have maximum votes in board’s voting system.

Sample 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

Sample Output

1 0 0 
1 2 6 
0 1 5 
1 0 0 

Submit

Source: Tehran, Asia Region - Regional 2008