Hide

Problem D
Anthony and Cora

Anthony and Cora play a very exciting game. Initially, Anthony has $N$ points and Cora has $M$ points. The game then goes on for several rounds, during each round, either Anthony wins or Cora wins, the loser of the round loses $1$ point while nothing happens to the winner of the round. The game ends when either Anthony or Cora has no points left, and the one still left with points is the winner of the game.

Cora promises Anthony a sweet prize if he wins the game, but will cruelly humiliate Anthony if he loses. Anthony can very accurately evaluate himself and perfectly predict that his probability of winning the round $i$ is exactly $p_ i$. Now, in order to decide whether to play this game with Cora or not, he needs to know the probability of him winning the game.

Help Anthony find his probability of winning!

Input

The first line contain integers $1\leq N,M\leq 1\, 000$. $N+M-1$ lines follow, with the $i$-th line containing $0\leq p_ i\leq 1$, $p_ i$ has at most $6$ decimal digits.

Output

Output a single line containing the probability of Anthony winning this game. Your answer will be considered correct if its absolute or relative error doesn’t exceed $10^{-6}$.

Sample Input 1 Sample Output 1
1 1
0.500000
0.500000
Sample Input 2 Sample Output 2
3 2
1.000000
0.000000
1.000000
0.000000
1.000000

Please log in to submit a solution to this problem

Log in