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
