Mario Party

A board is laid out in a straight line. The leftmost position is the start, the N cells between the start and the star are numbered 1 to N, and the star sits at position N+1.

On each turn the player rolls a die that shows every integer from 1 to S with equal probability, then moves forward by that many positions. An integer is written on the cell where the player stops: a positive number gives that many coins, a negative number takes that many away. The game ends after T turns.

The player does not have to stop exactly on the star. Passing over the star is enough to win it. There are no cells past the star, so no coins change hands there.

For example, let $N=10$, $S=4$, $T=5$, with the cells reading 100, 50, -20, 60, 30, -10, -30, -50, 20, 70 in order. Rolls of 2, 3, 4, 1, 1 stop on cells 2, 5, 9, 10 and then win the star, for a total of 170 coins. Rolls of 1, 3, 2, 4, 1 stop on cells 1, 4, 6, 10 and then win the star, for a total of 220 coins.

A bad board can make every route that wins the star end with a negative total. With $N=9$, $S=3$, $T=4$ and the cells reading 150, 100, -200, -100, -300, -100, -200, 100, 150, the best total that still wins the star is -100 coins. The star matters more, so the player wins it even while losing coins.

What is the maximum profit when the star is won within T turns?

The input holds at most 20 test cases and ends with a line that holds a single 0.

The first line of each test case holds N, S and T. N is the number of cells between the start and the star. ($2 \le N \le 200$, $2 \le S \le 10$, $N + 1 \le ST$, $T \le N + 1$) These conditions guarantee that at least one way to win the star within T turns exists.

After that line, N integers follow over one or more lines. The i-th integer is the number of coins gained or lost on stopping at cell i, and its absolute value is less than 10000.

For each test case, print the maximum profit when the star is won within T turns, one value per line.