CF724E.Goods transportation

There are n cities located along the one-way road. Cities are numbered from 1 to n in the direction of the road.

The i-th city had produced p__i units of goods. No more than s__i units of goods can be sold in the i-th city.

For each pair of cities i and j such that 1 ≤ i < j ≤ n you can no more than once transport no more than c units of goods from the city i to the city j. Note that goods can only be transported from a city with a lesser index to the city with a larger index. You can transport goods between cities in any order.

Determine the maximum number of produced goods that can be sold in total in all the cities after a sequence of transportations.

有 $n$ 座城市沿一条单向道路分布，城市按道路方向编号为 $1$ 至 $n$。

第 $i$ 座城市生产了 $p_i$ 单位货物。第 $i$ 座城市最多可售出 $s_i$ 单位货物。

对于每一对满足 $1 \le i < j \le n$ 的城市 $i$ 和 $j$，你至多可执行一次从城市 $i$ 向城市 $j$ 运输货物的操作，且每次运输量不超过 $c$ 单位。注意：货物只能从编号较小的城市运往编号较大的城市。你可以以任意顺序在城市间运输货物。

求经过一系列运输操作后，所有城市中总共最多可售出的货物数量。

The first line of the input contains two integers n and c (1 ≤ n ≤ 10 000, 0 ≤ c ≤ 109) — the number of cities and the maximum amount of goods for a single transportation.

The second line contains n integers p__i (0 ≤ p__i ≤ 109) — the number of units of goods that were produced in each city.

The third line of input contains n integers s__i (0 ≤ s__i ≤ 109) — the number of units of goods that can be sold in each city.

输入的第一行包含两个整数 $n$ 和 $c$（$1 \leq n \leq 10\,000$，$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$）—— 表示每个城市可销售商品的数量（单位）。

Print the maximum total number of produced goods that can be sold in all cities after a sequence of transportations.

输出经过一系列运输后，所有城市中可售出的商品总数的最大值。