Welcome to ZOJ
Information
Select Problem
Runs
Ranklist
ZOJ Problem Set - 2703
Selling Tickets

Time Limit: 10 Seconds      Memory Limit: 32768 KB      Special Judge

You are hired by a company Antarctic Railways for developing the new ticket selling system Express 3.14. The problem looks very simple: the only type of cars run by a company is a car that has 36 seats united to 9 four-seat compartments. The system gathers information about passengers that wish to travel together and distributes seats among passengers to satisfy them as much as possible.

In particular, given up to 36 ticket requests for travel, divided into groups of up to four people that wish to travel together, you have to assign seat numbers to passengers in a way to maximize the total satisfaction. A total satisfaction is the sum of satisfactions of each passenger. A satisfaction of each passenger is the product of the friendship coefficient of his group and the number of other passengers from his group that travel in the same compartment. For example, if the group of four with friendship coefficient 30 travels in one compartment, they increase the total satisfaction by 4·3·30=360 , and if they traveled in two compartments as two and two, they would increase the total satisfaction by 2·1·30 + 2·1·30 = 120 .

Input

There are mutilple cases in the input file.

The first line of each case contains m --- the number of groups. Next m lines contain descriptions of groups. Each group is described with the number of passengers in it (one to four), its friendship coefficient (positive integer number not exceeding 1000) and the identifiers of passengers in it. Each passenger is identified with some unique positive integer number not exceeding 100. The total number of passengers does not exceed 36. No passenger is listed in more than one group.

There is an empty line after each case.

Output

On the first line of the output case print the maximal possible total satisfaction. The next 9 lines must contain four integer numbers each --- the identifiers of passengers travelling in the corresponding compartment. If some seat remains unoccupied, output 0 for it.

There should be an empty line after each case.

Sample Input

11
3 30 1 2 3
3 30 4 5 6
3 30 7 8 9
3 30 10 11 12
3 30 13 14 15
3 30 16 17 18
3 30 19 20 21
3 30 22 23 24
3 30 25 26 27
4 10 28 29 30 31
4 10 32 33 34 35

Sample Output

1620
1 2 3 28
4 5 6 29
7 8 9 30
10 11 12 31
13 14 15 32
16 17 18 33
19 20 21 34
22 23 24 35
25 26 27 0


Source: Andrew Stankevich's Contest #9
Submit    Status