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 翻译