The director of the household appliance chain “Rodonit” was calculating the month’s losses. The time was over when buyers were taking away the purchased goods from a store immediately after buying them. Now they demanded a free delivery and wanted to be telephoned in advance in order to agree upon the time of delivery.

There are ten “Rodonit” stores in the city. The director understands that it is not always rational to deliver items directly from the stores where they were bought. On the outskirts of the city, there is a warehouse of household appliances, and next to the warehouse there is a garage. Every night employees compile a list of goods that have been bought during the day, with information about the buyers: names, addresses, and telephone numbers. These goods are delivered during the next day. The company has only one lorry for delivering goods. The lorry has a limited carrying capacity, therefore several trips are sometimes necessary to deliver the goods. The employees arrange the delivery schedule: which items should the lorry driver take from the warehouse for each trip and the order of visits to the buyers.

In order to save the fuel, the total length of the trips must be minimal. The employees use a city map to measure the distances between objects (which are the warehouse and the houses of the buyers from the list) and start the complicated optimization process. The following assumptions are made:

1. The distance between the warehouse and the garage is 0.
2. Let D(i, j) be the distance between objects i and j. Then for any objects i, j, k
   1. D(i, i) = 0.
   2. D(i, j) = D(j, i).
   3. D(i, k) ≤ D(i, j) + D(j, k).
3. In the end of each trip the lorry must return to the garage.
4. The sum of the masses of the goods carried by the lorry at one time must not exceed its carrying capacity.

The director must pay extra wages to the employees for their night work. In order to economize, he decided to employ a programmer who would write a program producing the delivery schedule.

In the first line there are the number of buyers M ≤ 20, the number of items N ≤ 50, and the carrying capacity of the lorry L_max ≤ 3000. In the following lines there is a matrix D of size (M+1)×(M+1) containing distances between the objects (the warehouse is assigned the number 0 and the buyers are assigned numbers from 1 to M). Each of the following N lines describes the corresponding item: its mass and the number of the buyer (an integer from 1 to M). All the masses and distances are integers in the range from 1 to 100.

In the first line output the number of trips that should be made. Then describe each trip giving the following information. The first line must contain the numbers of the items delivered during this trip, given in an arbitrary order and separated with a space (these numbers are in the range from 1 to N). The second line must contain the maximal load of the lorry during this trip (which is the total mass of the items being delivered). In the third line, output the number of objects in the order of traveling separated with a space. In the fourth line, output the total length of the trip. In the last line output the total length of all the trips. The blocks describing the trips must be separated from each other and from the first and last lines by an empty line.

Your program will pass a test if it produces an answer that is no worse than the answer produced by the jury’s program for the same data.