시간 제한메모리 제한제출정답맞힌 사람정답 비율
7 초 (추가 시간 없음) 1024 MB2912834.783%

문제

You are managing an archery team for a competition. Each team member has their own fixed probability of hitting a target.

The tournament works in a series of rounds. Your team has the same number of members as there are rounds in the tournament. In each round, exactly one of your team members will participate. Each team member will participate in exactly one round. You, being the manager, get to decide in what order the team members will compete. You must submit the order to the judges before the first round starts.

The competition has a scoreboard, which shows the total number of hits minus misses. The scoreboard starts at zero at the beginning of the competition, and is cumulative; it does not get reset across rounds. A hit will increase the score by $1$ while a miss will decrease it by $1$. The scoreboard can go below zero.

The competition organizers have specified a list of strictly increasing positive thresholds, one per round. In each round, the chosen team member will repeatedly shoot at a target until the scoreboard has absolute value equal to the threshold. Remember that the scoreboard does not get reset across rounds.

Given that you know the thresholds as well as all of your team members' abilities, find the maximum possible probability that you will end the tournament with a positive number of hits.

입력

The first line of input contains a single integer $n$ ($2 \le n \le 17$), which is both the number of team members on your team, and the number of rounds of the tournament.

Each of the next $n$ lines contains a single real number $p$ ($0.0 < p < 1.0$), which is the probability that the given team member will hit a target. The probabilities will have at most two digits after the decimal point.

Each of the next $n$ lines contains a single integer $s$ ($1 \le s \le 100$), which is the threshold score chosen by the competition organizers for the given round. These values are in strictly increasing order.

출력

Output a single real number, which is the maximum probability that you will end the tournament with a positive number of hits. This value must be accurate to within an absolute or relative error of $10^{-6}$.

예제 입력 1

4
0.7
0.6
0.4
0.3
2
4
6
8

예제 출력 1

0.9277221

출처

ICPC > Regionals > North America > Pacific Northwest Regional > 2021 ICPC Pacific Northwest Region > Division 1 D번

  • 문제를 만든 사람: Lewin Gan