A generic fast food chain had been cutting costs by hiring increasingly cheaper and less-trained staff, so now they have a problem – the cashiers can no longer be trusted to correctly apply combo discounts when customers do want fries with that. Management figures it would be easiest to just let computers figure out if there’s an applicable discount that could be applied to the order.
The input file DATA3.txt will contain 5 test cases. Each case will begin with the integer 0 ≤ N ≤ 10, the number of deals available, followed by N lines in the form of discount num_items item1 item2 ... . All of the prices are in cents, so a $1.42 discount would be just the integer 142. Each item is described by a single word, and spaces separate items. Each deal has at least one item and no more than five; this quantity is described by the second token, num_items. For example: 142 3 burger fries drink .
After the list of deals is an integer 1 ≤ M ≤ 10, the number of orders in the current test case, followed by M lines, each of the form: num_items item1 item2 ... .
The output file OUT3.txt will print the largest sum of discounts applicable to each order. A discount is applicable if every item listed on the discount description also appears in the order, and every such item had not already contributed to another discount. If there are conflicting applicable discounts (e.g. burger1+drink, burger2+drink, and the order is burger1+burger2+drink), pick the configuration that will produce the largest sum.
The sample’s explanation: The first case doesn’t have any discounts, so it’s 0 for every line. The second case has two discounts available. For order 2-1, only “burger1+fries” is applicable, so the discount is 100. For order 2-2, both “burger1+fries” and “burger2+fries” are possible, but there is only one item of “fries”, so we should pick the larger discount; that would be 150. For order 2-3, it’s the same as previous, but now there are two sets of “fries”, so we could separate the order into two separate discounts; 100+150 = 250. Ordered items don’t necessarily appear in the same order as the discount specification.
0
1
2 burger fries
2
100 2 burger1 fries
150 2 burger2 fries
3
3 burger1 fries fries
3 burger1 burger2 fries
4 burger1 burger2 fries fries
0
100
150
250