Every day on his way home, little Billy passes by his great aunt Clara Mitchum's house. Generally he stops in for a chat with his aunt and sometimes he asks for some lollies. When he does, she generally gives him some, but then adds now don't be asking for any more for another N days where N is some positive integer. If N = 1 that means he can ask for some on the next day, but for example if it is April 6 and N = 4 then he must wait until April 10 or later before asking for more lollies.
One day Billy happened to catch sight of the his aunt's calendar, and noted that each day was marked with two integers. He also noted that the first of these referred to the number of lollies the aunt's would give him on a particular day, and the second to the delay that would then be required before making another request. He copied down as much of the information as he could, and has passed it to you to analyse. His objective, of course, is to get as many lollies as he can.
Write a program which will report the total number of lollies that can be obtained by Billy, and provide a schedule for obtaining that amount. In the event that there are two or more ways to obtain the maximum number of lollies, Billy will choose the one where his first collection is as early as possible, and among all collections with that first date, his second collection is as early as possible, and so on.
The input text consists of a number of sets of unrelated problems. The first line of a set is a problem title consisting of a string of 1 to 20 letters. A single `#' on a line indicates the end of input.
The title line is followed by a sequence of day lines. Each problem set contains between 1 and 100 days, including the limits. In the given order, the first day line corresponds to day number 1, the second line to day number 2, the n-th line to day number n. Each day line consists of two integers separated by a single space:
an integer L, which is the number of lollies available on that day (1 <= L <= 100),
an integer N, which is the associated delay (1 <= N <= 100).
Sample Input
January
1 1
2 2
3 3
February
10 3
7 1
5 2
1 1
March
2 3
1 1
3 7
2 7
#
Sample Output
In January 4 lollies can be obtained:
On day 1 collect 1 lolly.
On day 3 collect 3 lollies.
In February 12 lollies can be obtained:
On day 2 collect 7 lollies.
On day 3 collect 5 lollies.
In March 4 lollies can be obtained:
On day 1 collect 2 lollies.
On day 4 collect 2 lollies.
I have a few ideas on how to go about this problem but, I'm new to dynamic programming in general. Sorry for the lengthy problem description, but I didn't want to leave any useful information out.
Any help is appreciated.
