Problem S
Bundles of Joy

For example, you can buy the “Chocolate Cakes” bundle which includes chocolate layer cake and black forest cake for $20. Or you can buy the “Fruity Cakes” bundle which includes lemon pound cake and key lime cake, also for $20. They offer an even bigger bundle that includes a slice of each of these cakes for an even lower price of $38.
You want to try out each dessert they offer. So, you need to buy some bundles to ensure you get at least one of each dessert. Of course, your goal is to do this while minimizing the amount of money you spend on bundles.
Finally, you make a few observations about the bundles they offer:
-
For any two bundles
and , either every dessert in is also in , every dessert in is also in , or there is no dessert in both and . -
The only way to buy an item individually is if it is in a bundle of size 1. Not all items are in such a bundle.
-
The pricing is not very well thought out. It may be cheaper to acquire items in a bundle
by buying some combination of other bundles rather than itself.
Input
The first line contains a single integer
Then
Each of the
Output
The output for each test case is a single line containing the minimum cost of purchasing bundles to ensure you get at least one of each item. This value is guaranteed to fit in a 32-bit signed integer.
Sample Input 1 | Sample Output 1 |
---|---|
4 4 3 20 2 1 2 20 2 3 4 38 4 1 2 3 4 2 3 5 1 1 10 2 1 2 4 1 2 2 2 1 1 1 5 2 2 1 1 2 2 1 1 1 1 1 |
38 9 5 1 |