AT_joi2023_yo2_d.貨物列車 (Freight Train)

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

IOI 铁道经营着货物运输。车站 $2, 3, \ldots, N$ 上各有一件货物，放在各自的车站。放在车站 $i$（$2 \leq i \leq N$）上的货物的价值为 $A_i$。

IOI 铁道拥有一列货物列车。列车起始时停靠在车站 $1$，并且可以在铁路线两端来回行驶。在每个车站上，可以将该车站的货物装载到列车上，也可以将列车上的货物卸下并暂时放在该站。

现在需要使用这辆货物列车，将车站 $2, 3, \ldots, N$ 上的货物运送到车站 $1$。但该列车最大只能同时装载 $W$ 件货物。即，任意时刻列车上货物数量不得超过 $W$。此外，受燃料限制，列车行驶的总距离不得超过 $D$。因此，可能无法将所有货物全部运回车站 $1$。

作为 IOI 铁道的社长 JOI 君，希望通过合理安排运输，使最终停放在车站 $1$ 上的货物总价值尽可能大。

请编写程序，根据所给货运列车及各站货物信息，计算可实现的车站 $1$ 上货物总价值的最大值。

输入格式如下：

$N\ W\ D\ A_2\ A_3\ \cdots\ A_N$

请输出最终可达到的车站 $1$ 上货物总价值的最大值，输出一行。

小子任务

1.（6 分）$W=1$，$A_i=1$（$2\leq i \leq N$）。
2.（9 分）$A_i=1$（$2\leq i \leq N$）。
3.（24 分）$W=1$。
4.（13 分）$N \leq 15$。
5.（24 分）$N \leq 50$。
6.（24 分）无其他附加条件。

样例解释 1

例如，按以下方式运行货物列车，则最终可使车站 $1$ 上货物总价值达到 $2$。

起初，货物列车在车站 $1$。

1. 驶往车站 $2$。
2. 将车站 $2$ 上价值为 $1$ 的货物装上列车。
3. 驶回车站 $1$。
4. 将该货物卸至车站 $1$。
5. 驶往车站 $4$。
6. 将车站 $4$ 上价值为 $1$ 的货物装上列车。
7. 驶回车站 $1$。
8. 将货物卸至车站 $1$。

此时总行驶距离为 $8$，满足“总距离不超过 $10$”的条件。

此时车站 $1$ 上货物总价值为 $2$，无法超过 $2$，因此输出 $2$。

该例满足所有小子任务的限制。

样例解释 2

例如，按以下方式运行货物列车，则最终可使车站 $1$ 上货物总价值达到 $5$。

起初，货物列车在车站 $1$。

1. 驶往车站 $5$。
2. 将车站 $5$ 上价值为 $1$ 的货物装上列车。
3. 驶往车站 $6$。
4. 将车站 $6$ 上价值为 $1$ 的货物装上列车。
5. 驶回车站 $1$。
6. 将两件价值为 $1$ 的货物全部卸至车站 $1$。
7. 驶往车站 $2$。
8. 将车站 $2$ 上价值为 $1$ 的货物装上列车。
9. 驶往车站 $3$。
10. 将车站 $3$ 上价值为 $1$ 的货物装上列车。
11. 驶往车站 $4$。
12. 将车站 $4$ 上价值为 $1$ 的货物装上列车。
13. 驶回车站 $1$。
14. 将三件价值为 $1$ 的货物全部卸至车站 $1$。

此时总行驶距离为 $16$，满足“总距离不超过 $16$”的条件。

此时车站 $1$ 上货物总价值为 $5$，无法超过 $5$，因此输出 $5$。

该例满足子任务 $2, 4, 5, 6$ 的限制。

样例解释 3

例如，按以下方式运行货物列车，则最终可使车站 $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$，无法超过 $100$，因此输出 $100$。

该例满足子任务 $4, 5, 6$ 的限制。

样例解释 4

该例满足子任务 $3, 4, 5, 6$ 的限制。

样例解释 5

该例满足子任务 $4, 5, 6$ 的限制。

约束条件

• $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$）。
• 所有输入数值均为整数。

由 ChatGPT 5 翻译