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 pi units of goods. No more than si 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 ≤ 109) — the number of cities and the maximum amount of goods for a single transportation.

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

The third line of input contains n integers si (0 ≤ si ≤ 109) — 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.

Examples

Input

3 0 1 2 3 3 2 1

Output

4

Input

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

Output

12

Input

4 3 13 10 7 4 4 7 10 13

Output

34

inputFormat

Input

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 pi (0 ≤ pi ≤ 109) — the number of units of goods that were produced in each city.

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

outputFormat

Output

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

Examples

Input

3 0 1 2 3 3 2 1

Output

4

Input

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

Output

12

Input

4 3 13 10 7 4 4 7 10 13

Output

34

样例

3 0
1 2 3
3 2 1

4

</p>