Problem Statement

At the yuki shop, items will be sold over the next $N$ days. On the morning of day $i$ $(1 \leq i \leq N)$, a new item priced at $A_i$ yen is added, and it remains in the shop until it is sold.

From now on, $1$ customer is scheduled to come per $1$ day. The wealth of the customer who comes on the evening of day $i$ $(1 \leq i \leq N)$ is $R_i$. Every customer buys "the cheapest item among those currently remaining" with probability $50\%$, and leaves without buying an item with probability $50\%$.

The satisfaction of the shopping is the sum, over all customers, of "wealth $\times$ price of the purchased item". A customer who leaves without buying an item has satisfaction $0$. Find the expected value of the satisfaction.

Input

$N$
$A_1$ $A_2$ $\cdots$ $A_N$
$R_1$ $R_2$ $\cdots$ $R_N$

Output

Output the expected value of the satisfaction. Your answer is considered correct if the absolute or relative error is at most $10^{-6}$.

Constraints

• $1 \leq N \leq 500$
• $1 \leq A_i \leq 1000$
• $1 \leq R_i \leq 1000$
• All input values are integers

Sample

2
4 6
9 3

25.5

4
1 1 1 1
1 1 1 1

2.0

8
3 1 4 1 5 9 2 6
5 3 5 8 9 7 9 3

50.75