Problem Statement

A and B like card games.
In this card game, there are $1000$ cards, with the integers from $1$ to $1000$ written on them, $1$ integer on each card, so that each integer appears once.
First, A and B are each dealt $N$ cards.
The game is very, very, very simple.
The game consists of $N$ matches.
In each match, each player freely plays $1$ card; the player whose card has the larger integer is the winner of that match and obtains as points the sum of the integers written on the $2$ played cards.
A card that has been played $1$ time in a match cannot be used $2$ times.
After the $N$ matches are over, the player with the larger total score is the winner of the game (if the scores are tied, there is no winner).
The cards have already been dealt: the cards dealt to A are $A_1,A_2,\ldots,A_N$, and the cards dealt to B are $B_1,B_2,\ldots,B_N$.
Compute the probability that A wins this game.

However, both A and B have a habit of using small cards early, and they choose the card to play in each match in the following way.
If A or B has only $1$ usable card, that player always plays that card.
If A has $2$ or more usable cards, A plays the card with the smallest integer among them with probability $P_A$, and the probabilities of choosing each of the other cards are all equal.
If B has $2$ or more usable cards, B plays the card with the smallest integer among them with probability $P_B$, and the probabilities of choosing each of the other cards are all equal.
The cards played by A and B are not influenced by the results of the game so far, the current state of the cards, and so on; they choose the cards to play independently of these.

Input

$N$ $P_A$ $P_B$
$A_1$ $A_2$ $\cdots$ $A_N$
$B_1$ $B_2$ $\cdots$ $B_N$

$1 \leq N \leq 20$
$0.500 \leq P_A, P_B \leq 0.999$, and $P_A,P_B$ each have at most $3$ digits after the decimal point
$1 \leq A_1,A_2,\ldots,A_N,B_1,B_2,\ldots,B_N \leq 1000$
$A_1,A_2,\ldots,A_N,B_1,B_2,\ldots,B_N$ are all distinct

Output

Output the probability that A wins this game.
Your answer is considered correct if the absolute error is at most $0.005 = 5 \times 10^{-3}$.

Sample

7 0.873 0.555
97 63 16 83 94 73 55
98 64 17 84 95 74 56

0.310081669035211

7 0.999 0.999
97 63 16 83 94 73 55
98 64 17 84 95 74 56

0.001479034961897

5 0.5 0.5
1 2 3 4 5
996 997 998 999 1000

0.000000000000000