← 返回题目列表

Codeforces · 724/E

E. 货物运输

中文机器翻译题面 查看原题

有 n 个城市位于单向公路沿线。城市沿道路方向从 1 到 n 编号。

第 i 个城市生产了 pi 单位的商品。第 i 个城市最多可销售 si 单位的商品。

对于每对城市 i 和 j,且 1 ≤ i < j ≤ n,您最多只能从城市 i 向城市 j 运输不超过 c 单位的货物。请注意,货物只能从指数较小的城市运输到指数较大的城市。您可以按任何顺序在城市之间运输货物。

确定经过一系列运输后,所有城市总共可以销售的最大生产商品数量。

输入

输入的第一行包含两个整数 n 和 c (1 ≤ n ≤ 10 000, 0 ≤ c ≤ 109)——城市数量和单次运输的最大货物数量。

第二行包含 n 个整数 pi (0 ≤ pi ≤ 109) — 每个城市生产的商品单位数。

输入的第三行包含n个整数si (0 ≤ si ≤ 109)——每个城市可以销售的商品单位数。

输出

打印一系列运输后可在所有城市销售的最大生产商品总数。

示例

输入 #1

3 0
1 2 3
3 2 1

输出 #1

4

输入 #2

5 1
7 4 2 1 0
1 2 3 4 5

输出 #2

12

输入 #3

4 3
13 10 7 4
4 7 10 13

输出 #3

34