Problem D
Clutch Game

The city of Piltover and Zaun is growing increasingly divided, and the council is struggling to find a good way to bring peace. That’s when Jayce comes up with the brilliant idea of having a friendly basketball game between Piltover and Zaun — after all, who wouldn’t love a game of basketball?!

Both cities assemble their best team and go at each other. There are $T$ seconds left in the game, and the score is tied. Team Piltover wins if and only if it has a strictly higher score than team Zaun when the time runs out. Each team alternates on offense, with team Piltover starting first. In each turn, the offensive team has at most $S$ seconds to make a shot — a 2 pointer or 3 pointer. If they fail to make a shot within the time limit, it will be an automatic turnover and the opposing team gains position. At each second of the first $S$ seconds of obtaining possession, the team may choose to shoot the ball and give up possession once they shoot (whether they make it or not). At each second, team Piltover’s probability of making a two pointer is $P_{a, 1}, P_{a, 2}, \dots , P_{a, S}$, the probability of making a three pointer is $Q_{a, 1}, Q_{a, 2}, \dots , Q_{a, S}$; similarly, team Zaun’s probability of making a two pointer is $P_{b, 1}, P_{b, 2}, \dots , P_{b, S}$, the probability of making a three pointer is $Q_{b_1}, Q_{b_2}, \dots , Q_{b_S}$.

Given that the teams know each others’ probability and assuming they each play perfectly to maximize their chances of winning, what is team Piltover’s chance of winning?

Input

The first line of input are two space-separated integers $T, S \: (1 \leq T, S \leq 1\, 000)$, where $T$ represents the number of seconds in the game, and $S$ represents the maximum amount of time a team has to make a shot.
The second line of input are $S$ space-separated real numbers $0 \le P_{a, 1}, P_{a, 2}, \dots , P_{a, S} \le 1$, where $P_{a, i}$ denotes the probability of team Piltover making a 2 pointer $i$ seconds in.
The third line of input are $S$ space-separated real numbers $0 \le Q_{a, 1}, Q_{a, 2}, \dots , Q_{a, S} \le 1$, where $Q_{a, i}$ denotes the probability of team Piltover making a 3 pointer $i$ seconds in.
The fourth line of input are $S$ space-separated real numbers $0 \le P_{b, 1}, P_{b, 2}, \dots , P_{b, S} \le 1$, where $P_{b, i}$ denotes the probability of team Zaun making a 2 pointer $i$ seconds in.
The fifth line of input are $S$ space-separated real numbers $0 \le Q_{b, 1}, Q_{b, 2}, \dots , Q_{b, S} \le 1$, where $Q_{b, i}$ denotes the probability of team Zaun making a 3 pointer $i$ seconds in.
All the probabilities are floating point numbers with at most $6$ digits after the decimal point.

Output

Output one line containing a single number, $0 \le p \le 1$, representing team Piltover’s chance of winning. Answers within a relative or absolute error of $10^{-6}$ will be accepted.

1 5
0.2 0.4 0.6 0.55 0.32
0.1 0.2 0.33 0.24 0.16
0.5 0.5 0.5 0.5 0.5
0.25 0.25 0.25 0.25 0.25

0.200000

3 2
0.5 0.5
0.25 0.4
0.6 0.4
0.3 0.3

0.300000