题目描述

IOI 铁路运营着一条铁路线。该铁路线上有 $N$ 个车站，沿直线依次排列，编号从 $1$ 到 $N$。对于每个 $i$（$1 \le i \le N-1$），车站 $i$ 与车站 $i+1$ 之间由一条长度为 $1$ 的线路连接。

IOI 铁路负责货物运输。在车站 $2, 3, \cdots, N$ 上各放置一件货物，车站 $i$（$2 \le i \le N$）上货物的价值为 $A_i$。

IOI 铁路拥有一列货运列车。该列车初始位于车站 $1$，可在 IOI 铁路线路上双向行驶。在每个车站，列车可以装载该站放置的货物，也可以卸下已装载的货物，或将货物留在该站。

现计划使用该货运列车，将车站 $2, 3, \cdots, N$ 上的货物运送到车站 $1$。但该列车最多只能装载 $W$ 件货物，即在任何时刻，列车上装载的货物数量不得超过 $W$ 件。此外，由于燃料限制，列车最多只能行驶总距离 $D$。因此，可能无法将所有货物运送到车站 $1$。

作为 IOI 铁路社长的 JOI 君，希望在满足上述条件的前提下，合理调度货运列车，使得最终在车站 $1$ 上的货物总价值尽可能大。

给定货运列车的信息以及各站货物的信息，编写一个程序，求出最终在车站 $1$ 上的货物总价值所能达到的最大值。

输入格式

输入数据按以下格式给出：

$N\ W\ D$

$A_2\ A_3\ \cdots\ A_N$

输出格式

在一行内输出最终在车站 $1$ 上的货物总价值所能达到的最大值。

4 1 10
1 1 1

2

7 3 16
1 1 1 1 1 1

5

5 2 12
40 30 20 10

100

5 1 11
2 7 1 8

10

9 3 14
54640 754112 604290 105866 591907 801383 502975 379373

2214425

提示

样例 1 解释

例如，若按以下方式运行货运列车，最终可在车站 $1$ 上获得总价值为 $2$ 的货物：

初始时，货运列车位于车站 $1$。

• 将列车驶向车站 $2$。
• 装载车站 $2$ 上价值为 $1$ 的货物。
• 将列车驶回车站 $1$。
• 将列车上价值为 $1$ 的货物卸至车站 $1$。
• 将列车驶向车站 $4$。
• 装载车站 $4$ 上价值为 $1$ 的货物。
• 将列车驶回车站 $1$。
• 将列车上价值为 $1$ 的货物卸至车站 $1$。

列车行驶的总距离为 $8$，满足“列车最多只能行驶总距离 $10$”的限制条件。

此时，最终在车站 $1$ 上的货物总价值为 $2$。由于无法使车站 $1$ 上的货物总价值达到 $3$ 或以上，故应输出 $2$。

该输入样例满足所有子任务的约束。

样例 2 解释

例如，若按以下方式运行货运列车，最终可在车站 $1$ 上获得总价值为 $5$ 的货物：

初始时，货运列车位于车站 $1$。

• 将列车驶向车站 $5$。
• 装载车站 $5$ 上价值为 $1$ 的货物。
• 将列车驶向车站 $6$。
• 装载车站 $6$ 上价值为 $1$ 的货物。
• 将列车驶回车站 $1$。
• 将列车上两个价值均为 $1$ 的货物全部卸至车站 $1$。
• 将列车驶向车站 $2$。
• 装载车站 $2$ 上价值为 $1$ 的货物。
• 将列车驶向车站 $3$。
• 装载车站 $3$ 上价值为 $1$ 的货物。
• 将列车驶向车站 $4$。
• 装载车站 $4$ 上价值为 $1$ 的货物。
• 将列车驶回车站 $1$。
• 将列车上三个价值均为 $1$ 的货物全部卸至车站 $1$。

列车行驶的总距离为 $16$，满足“列车最多只能行驶总距离 $16$”的限制条件。

此时，最终在车站 $1$ 上的货物总价值为 $5$。由于无法使车站 $1$ 上的货物总价值达到 $6$ 或以上，故应输出 $5$。

该输入样例满足子任务 2、4、5、6 的约束。

样例 3 解释

例如，若按以下方式运行货运列车，最终可在车站 $1$ 上获得总价值为 $100$ 的货物：

初始时，货运列车位于车站 $1$。

• 将列车驶向车站 $5$。
• 装载车站 $5$ 上价值为 $10$ 的货物。
• 将列车驶向车站 $4$。
• 装载车站 $4$ 上价值为 $20$ 的货物。
• 将列车驶向车站 $2$。
• 将列车上价值为 $10$ 和 $20$ 的货物卸至车站 $2$。
• 装载车站 $2$ 上价值为 $40$ 的货物。
• 将列车驶向车站 $3$。
• 装载车站 $3$ 上价值为 $30$ 的货物。
• 将列车驶回车站 $1$。
• 将列车上价值为 $30$ 和 $40$ 的货物卸至车站 $1$。
• 将列车驶向车站 $2$。
• 装载车站 $2$ 上价值为 $10$ 和 $20$ 的货物。
• 将列车驶回车站 $1$。
• 将列车上价值为 $10$ 和 $20$ 的货物卸至车站 $1$。

列车行驶的总距离为 $12$，满足“列车最多只能行驶总距离 $12$”的限制条件。

此时，最终在车站 $1$ 上的货物总价值为 $100$。由于无法使车站 $1$ 上的货物总价值达到 $101$ 或以上，故应输出 $100$。

该输入样例满足子任务 4、5、6 的约束。

数据范围

• $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 分）无额外约束。

翻译由 Qwen3-235B 完成。