화물 열차

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

IOI 철도는 화물도 취급한다. 역 $2, 3, \dots, N$에는 화물이 하나씩 놓여 있고, 역 $i$($2 \leq i \leq N$)에 놓인 화물의 가치는 $A_i$이다.

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

이 화물 열차로 역 $2, 3, \dots, N$에 놓인 화물을 역 1로 운송하려 한다. 다만 열차에는 화물을 $W$개 이하로만 실을 수 있다. 즉 어느 시점에서든 열차에 화물이 $W+1$개 이상 실려 있을 수는 없다. 또한 연료 사정으로 열차는 총 거리 $D$까지만 운행할 수 있다. 그래서 모든 화물을 역 1로 옮기지 못할 수도 있다.

IOI 철도의 사장 JOI 군은 이 조건 아래에서 열차를 적절히 운행해, 최종적으로 역 1에 놓이는 화물 가치의 합을 최대한 크게 만들고자 한다.

입력은 다음 형식으로 주어진다.

N W D
A_2 A_3 \dots A_N

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

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