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.

Input

The first line of the input contains two integers $*n*$ and $*c*$ ($1 ≤ *n* ≤ 10 000$, $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.

Output

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