你正在管理一支射箭队参加比赛。每位队员都有各自固定的命中目标概率。

比赛由一系列轮次组成。你的队伍人数与比赛轮次数量相同。在每一轮中，恰好有一名队员参赛。每位队员恰好参加一轮比赛。作为经理，你需要决定队员参赛的顺序。你必须在第一轮开始前将顺序提交给裁判。

比赛设有记分牌，显示命中次数减去失误次数的总和。记分牌在比赛开始时为零，且具有累积性；它不会在轮次之间重置。命中会使分数增加 1，而失误会使分数减少 1。记分牌的分数可以为负。

比赛组织者指定了一系列严格递增的正整数阈值，每轮一个。在每一轮中，选定的队员将反复射击目标，直到记分牌分数的绝对值等于该轮的阈值。请记住，记分牌在轮次之间不会重置。

已知各轮的阈值以及所有队员的能力，请找出比赛结束时总命中数大于总失误数（即最终分数为正）的最大可能概率。

输入格式

第一行包含一个整数 $n$ ($2 \le n \le 17$)，既是你的队员人数，也是比赛的轮次数量。

接下来的 $n$ 行，每行包含一个实数 $p$ ($0.0 < p < 1.0$)，表示该队员命中目标的概率。这些概率小数点后最多有两位数字。

接下来的 $n$ 行，每行包含一个整数 $s$ ($1 \le s \le 100$)，表示比赛组织者为该轮设定的阈值分数。这些值严格递增。

输出格式

输出一个实数，表示比赛结束时最终分数为正的最大概率。该值必须精确到绝对误差或相对误差不超过 $10^{-6}$。

样例

样例输入 1

4
0.7
0.6
0.4
0.3
2
4
6
8

样例输出 1

0.9277221