货物运输

• 时间限制：2 秒
• 内存限制：256 MiB

题目描述

有 $n$ 个城市沿一条单向道路排列，按道路方向依次编号为 $1$ 到 $n$。

城市 $i$ 生产了 $p_i$ 单位商品，最多能够销售 $s_i$ 单位商品。

对于任意一对满足 $1\le i<j\le n$ 的城市，可以从城市 $i$ 向城市 $j$ 运输至多 $c$ 单位商品；同一对城市至多进行一次运输。商品只能从编号较小的城市运往编号较大的城市，所有运输的执行顺序可以任意安排。

请计算经过若干次运输后，所有城市最多能够销售的商品总量。

输入格式

第一行包含两个整数 $n,c$，表示城市数量和每对城市之间的运输上限。

第二行包含 $n$ 个整数 $p_1,p_2,\ldots,p_n$，表示各城市的商品产量。

第三行包含 $n$ 个整数 $s_1,s_2,\ldots,s_n$，表示各城市的销售上限。

输出格式

输出所有城市能够销售的商品总量最大值。

样例输入 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

数据范围

对于所有数据，$1\le n\le10000$，$0\le c\le10^9$，$0\le p_i,s_i\le10^9$。