A10622 | 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.

The first line of the input contains two integers $n$ and $c$ ( $1<=n<=10000$ , $0<=c<=10^{9}$ ) — 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}<=10^{9}$ ) — 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}<=10^{9}$ ) — the number of units of goods that can be sold in each city.

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