Xiao Bao is preparing to go on a road trip.

There are $n$ stations on the road, numbered from $1$ to $n$. The distance between station $i$ and station $i+1$ is $v_i$ kilometers.

Every station on the road offers refueling. The price of one liter of fuel at station $i$ is $a_i$ yuan, and each station only sells an integer number of liters of fuel.

Xiao Bao wants to drive from station $1$ to station $n$. Initially, Xiao Bao is at station $1$ and the car's fuel tank is empty. It is known that the car's fuel tank is large enough to hold any amount of fuel, and each liter of fuel allows the car to travel $d$ kilometers. What is the minimum cost for Xiao Bao to refuel to drive from station $1$ to station $n$?

Input

The first line contains two positive integers $n$ and $d$, representing the number of stations on the road and the distance the car can travel per liter of fuel, respectively.

The second line contains $n-1$ positive integers $v_1, v_2, \dots, v_{n-1}$, representing the distances between the stations.

The third line contains $n$ positive integers $a_1, a_2, \dots, a_n$, representing the fuel prices at different stations.

Output

Output a single line containing one integer, representing the minimum cost for Xiao Bao to refuel to drive from station $1$ to station $n$.

Examples

Input 1

5 4
2 10 10 10 10
9 8 9 6 5

Output 1

79

Note 1

In the optimal plan: Xiao Bao buys $3$ liters of fuel at station $1$, $5$ liters of fuel at station $2$, and $2$ liters of fuel at station $4$.

Input 2

See road/road2.in and road/road2.ans in the contestant directory.

Constraints

For all test data, it is guaranteed that $1 \le n \le 10^5$, $1 \le d \le 10^5$, $1 \le v_i \le 10^5$, $1 \le a_i \le 10^5$.

Special Property A: The fuel price at station $1$ is the lowest.

Special Property B: For all $1 \le i < n$, $v_i$ is a multiple of $d$.