M. Minimum Parking Cost
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Henrique wants to park his car in the parking lot of the University of Brasília (UnB).

The parking spots are numbered from $$$1$$$ to $$$n$$$. Spot number $$$i$$$ is characterized by two numbers: its distance $$$d_i$$$ from the main entrance and the probability $$$p_i$$$ that it is free. Henrique visits the spots sequentially, starting from spot $$$1$$$. Upon arriving at spot $$$i$$$, two situations may occur:

  1. With probability $$$p_i$$$, spot $$$i$$$ is free. In this case, Henrique has two options: park in spot $$$i$$$ (Henrique is extremely fast, so we may consider that he takes $$$0$$$ seconds to park), or move on to the next spot, which is spot $$$i+1$$$ if $$$i \neq n$$$ and spot $$$1$$$ if $$$i = n$$$.

  2. With probability $$$1-p_i$$$, spot $$$i$$$ is occupied. In this case, Henrique is forced to continue to the next spot.

Each time Henrique moves on to the next spot, he spends $$$1$$$ second. After visiting spot $$$i$$$ once, it is possible that in subsequent visits its state will be different, since the UnB parking lot is very busy and a driver may have occupied or vacated the spot during the time Henrique took to return to it. This behaviour will be dictated by the probability $$$p_i$$$, which remains fixed throughout the entire problem.

Henrique wants to act so that the expected value of the sum of the total time spent choosing a spot and the distance of the spot where he finally parks is as small as possible. If Henrique acts optimally, what is this value?

Input

The first line of the input contains an integer $$$n$$$ $$$(2 \leq n \leq 3 \cdot 10^5)$$$.

The second line of the input contains $$$n$$$ integers $$$d_1, d_2, \dots, d_n$$$ $$$(1 \leq d_i \leq 10^6)$$$.

Finally, the third line of the input contains $$$n$$$ real numbers $$$p_1, p_2, \dots, p_n$$$ $$$(0.001 \leq p_i \leq 1)$$$. Each $$$p_i$$$ is given with at most 3 decimal places.

Output

Print a single real number: the expected value of the sum of the total time spent choosing a spot and the distance of the spot where he parks under the best strategy. Your answer will be considered correct if the absolute or relative error does not exceed $$$10^{-6}$$$. That is, if your answer is $$$a$$$ and the correct answer is $$$b$$$, your answer will be accepted if and only if $$$\frac{|a-b|}{\operatorname{max}(1, |b|)} \le 10^{-6}$$$.

Examples
Input
7
8 9 9 4 6 3 2
1 1 1 1 1 1 1
Output
7
Input
2
1 1000000
0.5 1
Output
3
Input
6
31 415 92 6535 89 79323
0.461 0.884 0.500 0.972 0.149 0.111
Output
38.01518438177870962136
Note

In the first test case, Henrique should park in spot number $$$4$$$. He takes a total of $$$3$$$ seconds to reach it, and it is at a distance of $$$4$$$ meters from the entrance, so the sum of the time spent and the distance is $$$3 + 4 = 7$$$. Since all spots are always free, he always achieves this value.