CF724E Goods transportation

有 $n$ 个城市沿着一条单向公路依次排列。城市按公路方向编号，从 $1$ 到 $n$。 第 $i$ 个城市生产了 $p_{i}$ 单位的商品。第 $i$ 个城市最多能销售 $s_{i}$ 单位的商品。 对于每一对城市 $i$ 和 $j$，满足 $1 \leq i < j \leq n$，你可以最多运输 $c$ 单位的商品，从城市 $i$ 到城市 $j$，并且每一对城市之间的运输至多进行一次。注意，商品只能从编号较小的城市运往编号较大的城市。城市间的运输顺序可以任意安排。 请你计算在进行若干次运输后，所有城市合计最多能够销售多少单位商品。

输入的第一行包含两个整数 $n$ 和 $c$（$1 \leq n \leq 10000$，$0 \leq c \leq 10^{9}$），分别表示城市的数量和每次运输的最大商品数量。 第二行包含 $n$ 个整数 $p_{i}$（$0 \leq p_{i} \leq 10^{9}$），表示每个城市生产的商品数量。 第三行包含 $n$ 个整数 $s_{i}$（$0 \leq s_{i} \leq 10^{9}$），表示每个城市最多能销售的商品数量。

输出进行若干次运输后，所有城市合计能销售的商品数量的最大值。

由 ChatGPT 5 翻译