RIPOFF

Business has been slow at Gleamin' Lemon Used Auto Sales. To bring in new customers, management created the Rebate Incentive Program Of Fabulous Fun (RIPOFF), a simple board game that lets a customer try to win a rebate on a car purchase.

Each square of the board is labeled with a rebate amount. The customer advances by spinning a spinner, and the amount on the square he lands on is added to his running rebate total. When he passes the end of the board, he is rewarded with the total rebate accumulated so far.

Given the company involved, it is no surprise that the fine print hides two catches. First, there is a limit on the number of turns allowed to finish the game; if the customer does not reach the end within that many turns, he loses the rebate. Second, some squares hold a negative amount, which is subtracted from the rebate. A very unlucky customer might even finish with a negative rebate.

Even so, management worries that someone might win an especially large rebate. Your job is to take a particular RIPOFF board configuration and determine the maximum rebate a customer could possibly obtain.

Movement rule: the customer starts just before the board begins (position 0), so spinning a 1 lands him on the first square. To finish, he must move past the last square and off the board. It need not be exact; any move that carries him off the board finishes the game.

For example, suppose a game lets you move 1 to 4 spaces per turn and must finish within 5 turns, with the board 100 50 -20 60 30 -10 -30 -50 20 70. Spinning 2, 3, 4, 1, 1 wins a total rebate of 50 + 30 + 20 + 70 = $170. The best possible rebate, however, is $220, obtained by spinning 1, 3, 2, 4, 1. Notice we did not land on every square with a positive number; had we done so, we could not have reached the end within 5 turns.

As another example, suppose a game lets you move up to 3 spaces per turn and must finish within 4 turns, with the board 150 100 -200 -100 -300 -100 -200 100 150. The highest possible rebate here is -$100 (a result that would please the management of Gleamin' Lemon). There may also be move sequences that never reach the end within the turn limit (for example, spinning a 1 every time). Although not finishing would actually be preferable to finishing with a negative rebate, this problem only considers move sequences that do reach the end within the turn limit.

The input consists of 1 to 20 data sets, followed by a line containing only 0.

The first line of a data set contains three space-separated integers $N$, $S$, and $T$:

• $N$: the total number of squares on the board, $2 \le N \le 200$.
• $S$: the maximum number of spaces you may advance in one turn, $2 \le S \le 10$.
• $T$: the maximum number of turns allowed, where $N + 1 \le S \cdot T$ and $T \le N + 1$.

The data set then lists, over one or more lines, the $N$ integers written on the board. Each number has magnitude less than 10000.

For each data set, output a single line containing 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, advancing 1 to $S$ spaces (inclusive) each turn. It is always possible to complete a game. However, a very large number of finishing turn sequences may exist, so choose your algorithm carefully.