Problem Description

An exploration team starts from $(0,0)$ and the destination is $(0,y)$. They carry equipment numbered from $1$ to $n$. The weight of equipment $i$ is $m_i$, and it must be placed at any position whose $x$-coordinate is $x_i$ (the $y$-coordinate can be any real number). All equipment must be placed in order. Before all equipment with smaller indices have been placed, even if the $x$-coordinate requirement is satisfied, the team still cannot place the current one.

When the total weight of the equipment carried by the team is $m$, the cost to move one unit of distance is $m + M$. Find the minimum total cost for the team to finish placing all equipment and arrive at the destination.

Multiple pieces of equipment can be placed at the same coordinate.

Input Format

The first line contains three positive integers $n$ ($1\le n \le 1\times 10^4$), $M$ ($0< M \le 30$), and $y$ ($0<y\le 2\times 10^5$), representing the number of devices, the basic movement cost, and the $y$-coordinate of the final destination.

The second line contains $n$ positive integers $m_i$ ($0< m_i\le 30$), representing the weight of device $i$. They are separated by spaces.

The third line contains $n$ integers $x_i$ ($|x_i|\le 1\times 10^4$), representing the required $x$-coordinate for device $i$.

Output Format

Output one line with one positive real number representing the final cost. If your answer is $a$ and the standard answer is $b$, then your answer is considered correct if and only if $\frac{|a - b|}{\max{(1, |b|)}} \le 10^{-6}$.

1 25 14
14
12

882.000000

Hint

Walk in a straight line to $(12,5)$, the distance is $13$, then walk in a straight line to $(0,14)$, the distance is $15$. The total cost is $13\times (25+14)+15\times 25=882$. There is no better solution than this.

Translated by ChatGPT 5