皮尔特沃夫和祖安两座城市之间的隔阂日益加深，议会正努力寻找一种带来和平的好方法。就在这时，杰斯提出了一个绝妙的主意：在皮尔特沃夫和祖安之间举办一场友谊篮球赛——毕竟，谁会不喜欢篮球赛呢？！

两座城市都组建了他们最顶尖的队伍并展开对决。现在比赛还剩 $T$ 秒，比分持平。当时间耗尽时，皮尔特沃夫队当且仅当其得分严格高于祖安队时才能获胜。两队轮流进攻，皮尔特沃夫队先攻。在每次进攻中，进攻方最多有 $S$ 秒的时间来完成一次投篮（两分球或三分球）。如果他们未能在时限内投篮，将自动失误并由对方获得球权。在获得球权的前 $S$ 秒的每一秒，球队可以选择投篮，并且一旦投篮（无论是否投中）就会失去球权。在控球的每一秒，皮尔特沃夫队投中两分球的概率分别为 $P_{a,1}, P_{a,2}, \dots, P_{a,S}$，投中三分球的概率分别为 $Q_{a,1}, Q_{a,2}, \dots, Q_{a,S}$；类似地，祖安队投中两分球的概率分别为 $P_{b,1}, P_{b,2}, \dots, P_{b,S}$，投中三分球的概率分别为 $Q_{b,1}, Q_{b,2}, \dots, Q_{b,S}$。

已知两队都清楚对方的投球命中率，且假设两队都完美发挥以最大化自己的获胜概率，求皮尔特沃夫队的获胜概率。

输入格式

输入的第一行包含两个空格分隔的整数 $T, S$（$1 \le T, S \le 1\,000$），其中 $T$ 表示比赛剩余的秒数，$S$ 表示每支球队每次进攻的最长持球时间。

第二行包含 $S$ 个空格分隔的实数 $0 \le P_{a,1}, P_{a,2}, \dots, P_{a,S} \le 1$，其中 $P_{a,i}$ 表示皮尔特沃夫队在控球第 $i$ 秒时投中两分球的概率。

第三行包含 $S$ 个空格分隔的实数 $0 \le Q_{a,1}, Q_{a,2}, \dots, Q_{a,S} \le 1$，其中 $Q_{a,i}$ 表示皮尔特沃夫队在控球第 $i$ 秒时投中三分球的概率。

第四行包含 $S$ 个空格分隔的实数 $0 \le P_{b,1}, P_{b,2}, \dots, P_{b,S} \le 1$，其中 $P_{b,i}$ 表示祖安队在控球第 $i$ 秒时投中两分球的概率。

第五行包含 $S$ 个空格分隔的实数 $0 \le Q_{b,1}, Q_{b,2}, \dots, Q_{b,S} \le 1$，其中 $Q_{b,i}$ 表示祖安队在控球第 $i$ 秒时投中三分球的概率。

所有概率均为实数，小数点后最多保留 6 位数字。

输出格式

输出一行，包含一个实数 $0 \le p \le 1$，代表皮尔特沃夫队的获胜概率。与真实答案的相对或绝对误差在 $10^{-6}$ 以内的输出将被接受。

样例

输入样例 1

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

输出样例 1

0.200000000

输入样例 2

3 2
0.5 0.5
0.25 0.4
0.6 0.4
0.3 0.3

输出样例 2

0.300000000