마리오 파티

일렬로 늘어선 보드가 있다. 맨 왼쪽은 출발점이고, 출발점과 별 사이에는 1번부터 N번까지 번호가 붙은 칸이 N개 있으며, 별은 N+1번 자리에 있다.

매 턴마다 플레이어는 1부터 S까지의 자연수가 균일한 확률로 나오는 주사위를 굴린 뒤, 나온 수만큼 앞으로 이동한다. 멈춘 칸에는 정수가 하나 쓰여 있어서, 그 수가 양수면 그만큼 코인을 얻고 음수면 그만큼 잃는다. 게임은 T턴이 지나면 끝난다.

별이 있는 자리에 정확히 멈출 필요는 없다. 별이 있는 자리를 지나가기만 해도 별을 얻는다. 별 뒤에는 칸이 없으므로 코인이 오가지 않는다.

예를 들어 $N=10$, $S=4$, $T=5$이고 칸에 쓰인 수가 순서대로 100, 50, -20, 60, 30, -10, -30, -50, 20, 70이라고 하자. 주사위가 2, 3, 4, 1, 1로 나오면 2번, 5번, 9번, 10번 칸에 멈춘 뒤 별을 얻고, 총 수익은 170코인이다. 1, 3, 2, 4, 1로 나오면 1번, 4번, 6번, 10번 칸에 멈춘 뒤 별을 얻고, 총 수익은 220코인이다.

보드가 나빠서 별을 얻는 모든 경로의 총 수익이 음수인 경우도 있다. $N=9$, $S=3$, $T=4$이고 칸에 쓰인 수가 150, 100, -200, -100, -300, -100, -200, 100, 150이면 별을 얻을 때의 최대 수익은 -100코인이다. 그래도 별이 더 중요하므로, 플레이어는 코인을 잃더라도 별을 얻으려 한다.

T턴 이내에 별을 얻을 때, 최대 수익은 얼마인가?

입력은 20개 이하의 테스트케이스로 이루어지고, 맨 끝에 0 하나가 놓인 줄이 온다.

각 테스트케이스의 첫 줄에 N, S, T가 주어진다. N은 출발점과 별 사이의 칸 수이다. ($2 \le N \le 200$, $2 \le S \le 10$, $N + 1 \le ST$, $T \le N + 1$) 이 조건 때문에 T턴 이내에 별을 얻는 방법이 반드시 존재한다.

그다음 줄부터 N개의 정수가 한 줄 이상에 걸쳐 주어진다. i번째 수는 i번 칸에 멈췄을 때 얻거나 잃는 코인의 수이고, 절댓값은 10000보다 작다.

각 테스트케이스마다 T턴 이내에 별을 얻을 때의 최대 수익을 한 줄에 하나씩 출력한다.