RIPOFF

「글리민 레몬 중고차 매장」의 장사가 통 신통치 않았다. 새 손님을 끌어들이려고 경영진은 「기막히게 즐거운 리베이트 혜택 프로그램(Rebate Incentive Program Of Fabulous Fun, 줄여서 RIPOFF)」을 만들었다. 이것은 손님이 자동차 구매 시 리베이트를 받을 수 있는지 겨루는 간단한 보드게임이다.

보드의 각 칸에는 리베이트 금액이 적혀 있다. 손님은 스피너를 돌려 나온 수만큼 앞으로 이동하며, 도착한 칸에 적힌 금액이 리베이트 합계에 더해진다. 보드의 끝을 지나면 그때까지 쌓인 리베이트 합계를 받는다.

다만 작은 글씨로 적힌 함정이 두 가지 있다. 첫째, 게임을 끝낼 수 있는 턴 수에 제한이 있다. 정해진 턴 안에 끝에 도달하지 못하면 리베이트를 받지 못한다. 둘째, 어떤 칸은 음수라서 리베이트에서 빠진다. 운이 아주 나쁜 손님은 리베이트 합계가 음수가 될 수도 있다.

이런 함정에도 경영진은 누군가 아주 큰 리베이트를 타 갈까 봐 걱정한다. 당신이 할 일은 주어진 게임판 설정에서 손님이 얻을 수 있는 최대 리베이트를 구하는 것이다.

이동 규칙: 손님은 보드가 시작되기 바로 앞(0번 위치)에서 출발한다. 따라서 1을 돌리면 첫 번째 칸에 도착한다. 게임을 끝내려면 마지막 칸을 지나 보드 밖으로 나가야 하는데, 정확히 맞출 필요는 없고 보드 밖으로 나가기만 하면 된다.

예를 들어 한 턴에 1~4칸을 이동할 수 있고 5턴 안에 끝내야 하며, 게임판이 100 50 -20 60 30 -10 -30 -50 20 70인 게임을 생각하자. 스피너를 2, 3, 4, 1, 1로 돌리면 50 + 30 + 20 + 70 = $170의 리베이트를 얻는다. 그러나 최선의 경우 얻을 수 있는 리베이트는 $220이며, 이는 1, 3, 2, 4, 1로 돌렸을 때다. 이때 양수가 적힌 칸을 모두 밟지는 않았음에 유의하라. 모두 밟았다면 5턴 안에 보드 끝까지 도달하지 못했을 것이다.

또 다른 예로, 한 턴에 최대 3칸씩 이동하고 4턴 안에 끝내야 하며 게임판이 150 100 -200 -100 -300 -100 -200 100 150인 게임을 보자. 이 게임에서 얻을 수 있는 최대 리베이트는 -$100이다(경영진이 흡족해할 결과다). 물론 매번 1만 돌리는 식으로 턴 제한 안에 끝에 도달하지 못하는 이동 순서도 있을 수 있다. 음수 리베이트로 끝내는 것보다 아예 끝내지 않는 편이 손님에게 유리하겠지만, 이 문제에서는 턴 제한 안에 보드 끝에 도달하는 이동 순서만 고려한다.

입력은 1개 이상 20개 이하의 데이터 집합으로 이루어지며, 마지막에는 0만 적힌 줄이 온다.

각 데이터 집합의 첫 줄에는 공백으로 구분된 세 정수 $N$, $S$, $T$가 주어진다.

• $N$: 보드의 전체 칸 수, $2 \le N \le 200$
• $S$: 한 턴에 전진할 수 있는 최대 칸 수, $2 \le S \le 10$
• $T$: 허용되는 최대 턴 수, $N + 1 \le S \cdot T$ 이고 $T \le N + 1$

이어서 한 줄 이상에 걸쳐 보드의 칸에 적힌 정수 $N$개가 주어진다. 각 수의 절댓값은 10000 미만이다.

각 데이터 집합에 대해, 게임을 끝냈을 때 얻을 수 있는 최대 리베이트를 한 줄에 출력한다.

게임을 끝내려면 한 턴에 1칸 이상 $S$칸 이하로 전진하여 최대 $T$턴 안에 총 $N + 1$칸을 전진해야 한다. 게임을 끝내는 것은 항상 가능하다. 다만 끝낼 수 있는 이동 순서가 매우 많을 수 있으므로 알고리즘 선택에 주의해야 한다.