H. Space Trip
time limit per test
1 second
memory limit per test
256 megabytes
input
standard input
output
standard output

You are embarking on an intergalactic space-trip! However, due to recent intergalactic events, the cost of spaceship fuel has been very erratic. Your trip can be thought of as a straight line with $$$n$$$ space fuel stations between you and your destination with position $$$p_i$$$ and cost $$$c_i$$$ per unit of fuel. You are initially at the first station. Special warp drive technology allows your ship to 'hop' from one position $$$x$$$ to another station at position $$$y$$$ for a cost of $$$\lceil\frac{f}{e} \rceil * |x - y|$$$ units of fuel, where $$$f$$$ is the amount of fuel you are carrying at position $$$x$$$ (after choose whether to buy any), and $$$e$$$ is your ship's fuel efficiency. You must always buy exactly enough fuel to get to your station. Your ship must have at least one unit of fuel to travel. Before you begin your trip, find the minimum amount you will need to pay to reach your destination!

Input

The first line of input will contain the integers $$$n (1 \leq n \leq 5000)$$$, $$$k (1 \leq k \leq 10^5)$$$, and $$$e (1 \leq e \leq 10^5)$$$, the number of space stations you will pass, your destination, and your ship's fuel efficiency.

The next line of input wlil contain $$$n$$$ ascending integers $$$p_i (0 \leq p_i \leq 10^5)$$$, the position of each fuel station. It is also guaranteed that the destination is reachable by spending a finite amount on fuel.

The last line of input will contain $$$n$$$ integers $$$c_i (1 \leq c_i \leq 10^5)$$$, the cost per unit of fuel at the $$$i-th$$$ station.

Output

Output the minimum amount you must pay to reach your destination.

Example
Input
5 70 30
0 20 30 40 60
2 3 4 3 7
Output
190