화물열차

문제

IOI 철도는 $1$ 개의 철도 노선을 운영하고 있다. IOI 철도선에는 일직선 위에 늘어선 $N$ 개의 역이 있으며, 순서대로 $1$ 부터 $N$ 까지의 번호가 붙어 있다. 각 $i$ ($1 \le i \le N - 1$) 에 대해, 역 $i$ 와 역 $i + 1$ 사이는 선로로 연결되어 있고, 그 길이는 $1$ 이다.

IOI 철도는 화물을 취급하고 있다. 역 $2, 3, \dots , N$ 에는 화물이 $1$ 개씩 놓여 있으며, 역 $i$ ($2 \le i \le N$) 에 놓여 있는 화물의 가치는 $A_{i}$ 이다.

IOI 철도는 화물열차를 $1$ 편성 보유하고 있다. 이 열차는 처음에 역 $1$ 에 있으며, IOI 철도선 위를 양방향으로 주행할 수 있다. 각 역에서는 그 역에 놓여 있는 화물을 열차에 싣거나, 열차에 실려 있는 화물을 내려서 그 역에 놓아둘 수 있다.

이 화물열차를 이용하여 역 $2, 3, \dots , N$ 에 놓여 있는 화물을 역 $1$ 로 수송하려고 한다. 단, 이 열차에는 화물을 $W$ 개 이하로만 실을 수 있다. 즉, 어느 시점에서도 열차에 화물이 $W + 1$ 개 이상 실려 있는 것은 허용되지 않는다. 또한 이 열차는 연료 사정상 최대 총 거리 $D$ 만큼만 주행할 수 있다. 그렇기 때문에 모든 화물을 역 $1$ 로 수송할 수는 없을지도 모른다.

IOI 철도의 사장인 JOI 군은 이 조건 하에서 화물열차를 적절히 주행시켜, 최종적으로 역 $1$ 에 놓여 있는 화물의 가치의 합을 가능한 한 크게 하고 싶다.

화물열차의 정보와 각 역에 놓여 있는 화물의 정보가 주어질 때, 최종적으로 역 $1$ 에 놓여 있는 화물의 가치의 합으로 달성 가능한 최댓값을 구하는 프로그램을 작성하시오.

제한

• $2 \le N \le 450$.
• $1 \le W \le N - 1$.
• $2 \le D \le N^{2} - N$.
• $1 \le A_{i} \le 1\,000\,000$ ($2 \le i \le N$).
• 입력되는 값은 모두 정수이다.

서브태스크

1. ($6$ 점) $W = 1$, $A_{i} = 1$ ($2 \le i \le N$).
2. ($9$ 점) $A_{i} = 1$ ($2 \le i \le N$).
3. ($24$ 점) $W = 1$.
4. ($13$ 점) $N \le 15$.
5. ($24$ 점) $N \le 50$.
6. ($24$ 점) 추가 제약이 없다.

입력

입력은 다음 형식으로 주어진다.
$N$ $W$ $D$
$A_{2}$ $A_{3}$ $\dots$ $A_{N}$

출력

최종적으로 역 $1$ 에 놓여 있는 화물의 가치의 합으로 달성 가능한 최댓값을 $1$ 줄로 출력한다.

예제 입력 1

4 1 10
1 1 1

예제 출력 1

2

예를 들어, 다음과 같이 화물열차를 주행시키면 최종적으로 역 $1$ 에 놓여 있는 화물의 가치의 합을 $2$ 로 만들 수 있다.

처음에 화물열차는 역 $1$ 에 있다.

1. 화물열차를 역 $2$ 로 주행시킨다.
2. 역 $2$ 에 놓여 있는 가치 $1$ 의 화물을 화물열차에 싣는다.
3. 화물열차를 역 $1$ 로 주행시킨다.
4. 화물열차에 실려 있는 가치 $1$ 의 화물을 역 $1$ 에 놓는다.
5. 화물열차를 역 $4$ 로 주행시킨다.
6. 역 $4$ 에 놓여 있는 가치 $1$ 의 화물을 화물열차에 싣는다.
7. 화물열차를 역 $1$ 로 주행시킨다.
8. 화물열차에 실려 있는 가치 $1$ 의 화물을 역 $1$ 에 놓는다.

열차가 주행한 총 거리는 $8$ 이며, 열차가 총 거리 $10$ 이하로만 주행할 수 있다는 조건을 만족한다.

이때 최종적으로 역 $1$ 에 놓여 있는 화물의 가치의 합은 $2$ 이다. 최종적으로 역 $1$ 에 놓여 있는 화물의 가치의 합을 $3$ 이상으로 만들 수는 없으므로, $2$ 를 출력한다.

이 예제는 모든 서브태스크의 제약을 만족한다.

예제 입력 2

7 3 16
1 1 1 1 1 1

예제 출력 2

5

예를 들어, 다음과 같이 화물열차를 주행시키면 최종적으로 역 $1$ 에 놓여 있는 화물의 가치의 합을 $5$ 로 만들 수 있다.

처음에 화물열차는 역 $1$ 에 있다.

1. 화물열차를 역 $5$ 로 주행시킨다.
2. 역 $5$ 에 놓여 있는 가치 $1$ 의 화물을 화물열차에 싣는다.
3. 화물열차를 역 $6$ 으로 주행시킨다.
4. 역 $6$ 에 놓여 있는 가치 $1$ 의 화물을 화물열차에 싣는다.
5. 화물열차를 역 $1$ 로 주행시킨다.
6. 화물열차에 실려 있는 $2$ 개의 가치 $1$ 의 화물을 모두 역 $1$ 에 놓는다.
7. 화물열차를 역 $2$ 로 주행시킨다.
8. 역 $2$ 에 놓여 있는 가치 $1$ 의 화물을 화물열차에 싣는다.
9. 화물열차를 역 $3$ 으로 주행시킨다.
10. 역 $3$ 에 놓여 있는 가치 $1$ 의 화물을 화물열차에 싣는다.
11. 화물열차를 역 $4$ 로 주행시킨다.
12. 역 $4$ 에 놓여 있는 가치 $1$ 의 화물을 화물열차에 싣는다.
13. 화물열차를 역 $1$ 로 주행시킨다.
14. 화물열차에 실려 있는 $3$ 개의 가치 $1$ 의 화물을 모두 역 $1$ 에 놓는다.

열차가 주행한 총 거리는 $16$ 이며, 열차가 총 거리 $16$ 이하로만 주행할 수 있다는 조건을 만족한다.

이때 최종적으로 역 $1$ 에 놓여 있는 화물의 가치의 합은 $5$ 이다. 최종적으로 역 $1$ 에 놓여 있는 화물의 가치의 합을 $6$ 이상으로 만들 수는 없으므로, $5$ 를 출력한다.

이 예제는 서브태스크 $2, 4, 5, 6$ 의 제약을 만족한다.

예제 입력 3

5 2 12
40 30 20 10

예제 출력 3

100

예를 들어, 다음과 같이 화물열차를 주행시키면 최종적으로 역 $1$ 에 놓여 있는 화물의 가치의 합을 $100$ 으로 만들 수 있다.

처음에 화물열차는 역 $1$ 에 있다.

1. 화물열차를 역 $5$ 로 주행시킨다.
2. 역 $5$ 에 놓여 있는 가치 $10$ 의 화물을 화물열차에 싣는다.
3. 화물열차를 역 $4$ 로 주행시킨다.
4. 역 $4$ 에 놓여 있는 가치 $20$ 의 화물을 화물열차에 싣는다.
5. 화물열차를 역 $2$ 로 주행시킨다.
6. 화물열차에 실려 있는 가치 $10$ 의 화물과 가치 $20$ 의 화물을 역 $2$ 에 놓는다.
7. 역 $2$ 에 놓여 있는 가치 $40$ 의 화물을 화물열차에 싣는다.
8. 화물열차를 역 $3$ 으로 주행시킨다.
9. 역 $3$ 에 놓여 있는 가치 $30$ 의 화물을 화물열차에 싣는다.
10. 화물열차를 역 $1$ 로 주행시킨다.
11. 화물열차에 실려 있는 가치 $30$ 의 화물과 가치 $40$ 의 화물을 역 $1$ 에 놓는다.
12. 화물열차를 역 $2$ 로 주행시킨다.
13. 역 $2$ 에 놓여 있는 가치 $10$ 의 화물과 가치 $20$ 의 화물을 화물열차에 싣는다.
14. 화물열차를 역 $1$ 로 주행시킨다.
15. 화물열차에 실려 있는 가치 $10$ 의 화물과 가치 $20$ 의 화물을 역 $1$ 에 놓는다.

열차가 주행한 총 거리는 $12$ 이며, 열차가 총 거리 $12$ 이하로만 주행할 수 있다는 조건을 만족한다.

이때 최종적으로 역 $1$ 에 놓여 있는 화물의 가치의 합은 $100$ 이다. 최종적으로 역 $1$ 에 놓여 있는 화물의 가치의 합을 $101$ 이상으로 만들 수는 없으므로, $100$ 을 출력한다.

이 예제는 서브태스크 $4, 5, 6$ 의 제약을 만족한다.

예제 입력 4

5 1 11
2 7 1 8

예제 출력 4

10

이 예제는 서브태스크 $3, 4, 5, 6$ 의 제약을 만족한다.

예제 입력 5

9 3 14
54640 754112 604290 105866 591907 801383 502975 379373

예제 출력 5

2214425

이 예제는 서브태스크 $4, 5, 6$ 의 제약을 만족한다.