Chain shopping is a new scheme introduced at a Mall to promote sale. Mall offers
normal discount on every item. Under the scheme a customer makes a list of distinct items to be
purchased. The list is called a purchase chain. For the kth
item in the chain Mall offers k times
the normal discount. This policy attracts customers to form long judicious chains. Assume that
an item under sale is identified by an integer ID and normal discount D offered for an item is an
amount in whole number.
Chain shopping is permitted under certain conditions. Any one of the available items
may be included as the first item in the purchase chain. However for any other item in the
purchase chain option is dependent on the previous selection. For each item ID Mall displays
prominently a list P(ID) of next potential items. If ID is in the chain then the next item could only
be any one of the items listed in P(ID). For example if Mall has four items with ID 24 29 61 81
and next potential items P(24), P(29), P(61) and P(81) are respectively 24: 29 61 29: 24 61 81
61: 24 81 29 81: 24 61 then the chain of three items 61 81 24 is valid while the chain 61 24 81 is
invalid.
Write a program to print purchase chain(s) of specified length L, for which the total
discount MD is maximum, given ID and D for each item under sale and all lists of next potential
items.
Input contains multiple test cases. Each case contains three lines.
The 1st line gives an integer specifying L.
The 2nd line gives a certain number (assume 20 or less) of pairs of integers in an arbitrary order. Each pair represents ID and D in order, for an item under sale.
The 3rd line gives all lists of potential items in the form of a string of integers, space and colon (:). An integer n followed by colon identifies the beginning of a list. Integers separated by space that follow colon, identify items in the list. Either the end of the line or the beginning of another list indicates the end of a list.
Input terminates with an input 0 as the first input for a test case.
For each test case the 1st line contains two integers N and MD. Integer N is the total number of purchase chains for each one of which the total discount is MD. Each of the following N lines contains one chain and chains appear in lexicographic order.
3 24 30 81 20 29 40 61 50 24: 81 29 81: 24 29 61 29: 81 61: 81 24 4 24 20 29 15 61 10 81 5 24: 29 61 29: 24 61 81 61: 24 81 29 81: 24 61 0
2 230 29 81 61 61 24 29 1 150 81 61 29 24
Migrated from old NTUJ.
ICPC Kanpur, 2008
| No. | Testdata Range | Score |
|---|