Calgary Collegiate Programming Competition 2017

Start

2017-03-18 20:00 CET

Calgary Collegiate Programming Competition 2017

End

2017-03-19 00:00 CET
The end is near!
Contest is over.
Not yet started.
Contest is starting in -247 days 16:38:50

Time elapsed

4:00:00

Time remaining

0:00:00

Problem A
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