1994 ACM Scholastic Programming Contest Finals

sponsored by Microsoft ®

Problem D
Package Pricing

The Green Earth Trading Company sells 4 different sizes of energy-efficient fluorescent light bulbs for use in home lighting fixtures. The light bulbs are expensive, but last much longer than ordinary incandescent light bulbs and require much less energy. To encourage customers to buy and use the energy-efficient light bulbs, the company catalogue lists special packages which contain a variety of sizes and numbers of the light bulbs. The price of a package is always substantially less than the total price of the individual bulbs in the package. Customers typically want to buy several different sizes and numbers of bulbs. You are to write a program to determine the least expensive collection of packages that satisfy any customer's request.

Input

The input file is divided into two parts. The first one describes the packages which are listed in the catalogue. The second part describes individual customer requests. The 4 sizes of light bulbs are identified in the input file by the characters "a", "b", "c", and "d".

The first part of the input file begins with an integer n (1<= n <=50) indicating the number of packages described in the catalogue. Each of the n lines that follows is a single package description. A package description begins with a catalogue number (a positive integer) followed by a price (a real number), and then the sizes and corresponding numbers of the light bulbs in the package. Between 1 and 4 different sizes of light bulbs will be listed in each description. The listing format for these size-number pairs is a blank, a character ("a", "b", "c", or "d") representing a size, another blank, and then an integer representing the number of light bulbs of that size in the package. These size-number pairs will not appear in any particular order, and there will be no duplicate sizes listed in any package. The following line describes a package with catalogue number 210 and price $76.95 which contains 3 size "a" bulbs, 1 size "c" bulb, and 4 size "d" bulbs. 

        210 76.95 a 3 c 1 d 4
The second part of the input file begins with a line containing a single positive integer m representing the number of customer requests. Each of the remaining m lines is a customer request. A listing of sizes and corresponding numbers of light bulbs constitutes a request. Each list contains only the size-number pairs, formatted the same way that the size-number pairs are formatted in the catalogue descriptions. Unlike the catalogue descriptions, however, a customer request may contain duplicate sizes. The following line represents a customer request for 1 size "a" bulb, 2 size "b" bulbs, 2 size "c" bulbs, and 5 size "d" bulbs. 

	a 1 d 5 b 1 c 2 b 1

Output

For each request, print the customer number (1 through m, 1 for the first customer request, 2 for the second, ..., m for the mth customer), a colon, the total price of the packages which constitute the least expensive way to fill the request, and then the combination of packages that the customer should order to fill that request.

Prices should be shown with exactly two significant digits to the right of the decimal. The combination of packages must be written in ascending order of catalogue numbers. If more than one of the same type package is to be ordered, then the number ordered should follow the catalogue number in parentheses. You may assume that each customer request can be filled. In some cases, the least expensive way to fill a customer request may contain more light bulbs of some sizes than necessary to fill the actual request. This is acceptable. What matters is that the customers receive at least what they request.

Sample Input 

5
10 25.00 b 2
502 17.95 a 1
3 13.00 c 1
55 27.50 b 1 d 2 c 1
6 52.87 a 2 b 1 d 1 c 3
6
d 1
b 3
b 3 c 2
b 1 a 1 c 1 d 1 a 1
b 1 b 2 c 3 c 1 a 1 d 1
b 3 c 2 d 1 c 1 d 2 a 1

Output for the Sample Input

1:   27.50 55
2:   50.00 10(2)
3:   65.50 3 10 55
4:   52.87 6
5:   90.87 3 6 10
6:  100.45 55(3) 502