#214416. [JOI2023 预选赛 R2] 货物列车 / Freight Train

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

IOI 铁路负责货物运输。在车站 上各放置一件货物，车站 （）上货物的价值为 。

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

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

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

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

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

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

样例输入 1

4 1 10
1 1 1

样例输出 1

2

样例输入 2

7 3 16
1 1 1 1 1 1

样例输出 2

5

样例输入 3

5 2 12
40 30 20 10

样例输出 3

100

样例输入 4

5 1 11
2 7 1 8

样例输出 4

10

样例输入 5

9 3 14
54640 754112 604290 105866 591907 801383 502975 379373

样例输出 5

2214425

样例 1 解释

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

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

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

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

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

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

样例 2 解释

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

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

• 将列车驶向车站 。
• 装载车站 上价值为 的货物。
• 将列车驶向车站 。
• 装载车站 上价值为 的货物。
• 将列车驶回车站 。
• 将列车上两个价值均为 的货物全部卸至车站 。
• 将列车驶向车站 。
• 装载车站 上价值为 的货物。
• 将列车驶向车站 。
• 装载车站 上价值为 的货物。
• 将列车驶向车站 。
• 装载车站 上价值为 的货物。
• 将列车驶回车站 。
• 将列车上三个价值均为 的货物全部卸至车站 。

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

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

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

样例 3 解释

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

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

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

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

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

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

数据范围

• 。
• 。
• 。
• （）。
• 所有输入值均为整数。

子任务

1. （6 分），且 （）。
2. （9 分）（）。
3. （24 分）。
4. （13 分）。
5. （24 分）。
6. （24 分）无额外约束。

翻译由 Qwen3-235B 完成。