Business has been slow at Gleaming Lemon Used Auto Sales. In an effort to bring in new customers, management has created the Rebate Incentive Program Of Fabulous Fun (RIPOFF). This is a simple game which allows customers to try to win a rebate on an automobile purchase. The RIPOFF game is a board game where each square is labeled with a rebate amount. The customer advances through the board by spinning a spinner. Each square he or she lands on adds to his or her total rebate amount. When the customer reaches the end of the board, he or she is rewarded with the total rebate amount.
Of course, given the company involved, it should come as no surprise that there are a couple of catches written in the fine print. The first is that there is a limit to the number of turns that the customer has to finish the game. If the customer does not reach the end within the allotted number of turns, then the customer loses his or her rebate. The second is that some of the squares actually have a negative amount, which subtract from the rebate instead of adding to it! A particularly unlucky customer might even come out of the game with a negative rebate.
Even with these catches, the management of Gleaming Lemon is concerned that someone could win a particularly large rebate, something they would like to avoid at all costs. Your job is to take a particular configuration for the RIPOFF game and determine the maximum rebate a customer could possibly obtain.
For example, consider the game board below. Assume we have 5 turns to finish the game, and each turn we can move between 1 and 4 spaces, depending on what we spin. Note that we start just before the beginning of the board; so spinning a 1 causes us to land on the first square. Also note that we end by landing past the ending of the board. (This does not have to be exactly one past the end of the board; any number that takes us off of the board suffices.
The illustration shows two different possible ways that the game might proceed. Following the arrows on the top, if we spin a 2, 3, 4, 1, and 1, respectively, we will win a total rebate of 50 + 30 + 20 + 70 = $170. However, the best possible rebate we could win would be $220. We would win this amount if we spun a 1, 3, 2, 4, and 1, respectively, as shown by the lower path. Notice that we did not land on every square with a positive number; if we had, we would not have been able to make it to the end of the board before our 5 turns were used up.
The next illustration (above) shows a game where we have 4 turns to finish the game, and can move up to 3 spaces each turn. Again, two different paths are shown: the one on top earning a rebate of –$150; and the one on bottom earning a rebate of –$100. In fact, –$100 is the highest possible rebate we could earn for this game (a fact that would no doubt please the management of Gleaming Lemon)! Of course, there also might be a sequence of moves in which we do not reach the end before the turn limit; e.g., spinning a 1 every time. Although not finishing would actually be preferable to finishing with a negative rebate, in this problem we are only going to consider sequences of moves which allow us to reach the end before the turn limit is up.
The input consists of one to twenty data sets, followed by a line containing only 0.
The first line of a data set contains three space separated integers N, S, T where
N is the total number of squares on the board, 2 ≤ N ≤ 200,
S is the maximum number of spaces that you may advance in each turn, 2 ≤ S ≤ 10, and
T is the maximum number of turns allowed, where N + 1 ≤ ST and T ≤ N + 1.
The data set follows, with one or more lines containing a total of N integers, representing the numbers on the board. Each number has magnitude less than 10000.
10 4 5 100 50 -20 60 30 -10 -30 -50 20 70 9 3 4 150 100 -200 -100 -300 -100 -200 100 150 0
The output for each data set is one line containing just the maximum possible rebate that can be earned by completing the game.
To complete the game, you must advance a total of N + 1 spaces in at most T turns, each turn advancing from 1 to S spaces, inclusive. Assume that it will always be possible to complete a game. However, there may be a (very) large number of different turn sequences that will finish, so you will need to be careful in choosing your algorithm.
The sample input data corresponds to the games in the illustrations above.
220 -100