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