Trading
Once there was some trade on Timboektoe, but it ended after a short time. After reading this story you will understand why. At that time Timboektoe was quite popular, because it was the only place in the world where people knew how to make a ‘flut’. The end of the trade on Timboektoe meant the end of the trade in fluts, and very few people nowadays know what a flut actually is. Fluts were manufactured in schuurs. Whenever a flut was finished it was packed in a box, which was then placed on top of the pile of previously produced fluts. On the side of each box the price was written. The price depended on the time it took to manufacture the flut. If all went well, a flut would cost one or two florins, but on a bad day the price could easily rise to 15 florins or more. This had nothing to do with quality; all fluts had the same value. In those days fluts sold for 10 florins each in Holland. Transportation costs were negligible since the fluts were taken as extra on ships that would sail anyway. When a Dutch merchant went to Timboektoe, he had a clear purpose: buy fluts, sell them in Holland, and maximize his profits. Unfortunately, the Timboektoe way of trading fluts made this more complicated than one would think. One would expect that merchants would simply buy the cheapest fluts, and the fluts that cost more than 10 florins would remain unsold. Unfortunately, all schuurs on Timboektoe sold their fluts in a particular order. The box on top of the pile was sold first, then the second one from the top, and so on. So even if the fifth box from the top was the cheapest one, a merchant would have to buy the other four boxes above to obtain it. As you can imagine, this made it quite difficult for the merchants to maximize their profits by buying the right set of fluts. Not having computers to help with optimization, they quickly lost interest in trading fluts at all. In this problem, you are given the description of several schuur piles. You have to calculate the maximum profit a merchant can obtain by buying fluts from the piles according to the restrictions given above. In addition, you have to determine the number of fluts he has to buy to achieve this profit.
The input describes several test cases. The first line of input for each test case contains a single integer Z, the number of schuurs in the test case. This is followed by Z lines, each describing a pile of fluts. The first number in each line is the number E of boxes in the pile. Following it are E positive integers, indicating the prices (in florins) of the fluts in the stack, given from top to bottom. The input is terminated by a description starting with Z = 0. This description should not be processed.
For each test case, print the case number (1, 2, …). Then print two lines, the first containing the maximum profit the merchant can achieve. The second line should specify the number of fluts the merchant has to buy to obtain this profit. If this number is not uniquely determined, print the possible values in increasing order. If there are more than ten possible values, print only the 10 smallest. Display a blank line between test cases.
Example input
1
6 12 3 10 7 16 5
2
5 7 3 11 9 10
9 1 2 3 4 10 16 10 4 16
0
Example output
schuurs 1
Maximum profit is 8.
Number of fluts to buy: 4
schuurs 2
Maximum profit is 40.
Number of fluts to buy: 6 7 8 9 10 12 13