题目内容

一位神枪手即将参加一场射击锦标赛，赛程中共有 $n$ 个移动标靶依次出现，编号从 $1$ 到 $n$。

对于第 $i$ 个标靶，如果他选择开火，则命中的概率为 $p_i$，命中可获得 $1$ 分；每次开火后，枪械会有 $q_i$ 的概率过热。一旦过热，他将无法对第 $i+1$ 个标靶开火（无论第 $i$ 个标靶是否命中）。过热状态只会持续一个标靶的间隔：即使跳过第 $i+1$ 个标靶不开火，枪械也会在第 $i+1$ 个标靶结束后自动冷却，后续的比赛不受影响。

枪手在面对每个标靶时可以自由选择开火或跳过。跳过时不会得分，也不会引起过热。

请你为枪手设计一个最优策略，最大化整个赛季命中次数的数学期望。

【约束】

• 标靶数量 $n$ 满足 $1 \le n \le 10^6$。
• 对于每个 $i$，概率 $p_i$ 和 $q_i$ 均为实数，满足 $0 \le p_i, q_i \le 1$。
• 你的答案与标准答案的绝对误差或相对误差不超过 $10^{-6}$ 即视为正确。

输入描述

第一行输入一个整数 $n$，表示标靶的数量。 接下来 $n$ 行，每行包含两个实数 $p_i$ 和 $q_i$，依次表示第 $i$ 个标靶的命中概率和开火后过热的概率。

输出描述

输出一个实数，表示能够达到的最大期望得分。答案的相对或绝对误差不超过 $10^{-6}$ 即可接受。

样例1

输入

1
0.8 0.3

输出

0.8000000000

说明

只有 1 场比赛，成功打铁的概率 p1=0.8，赛后禁赛的概率 q1=0.3。选择参加可获得期望打铁次数 0.8，选择不参加为 0。因此最大期望打铁次数为 0.8。

样例2

输入

2
0.9 1.0
0.5 0.5

输出

0.9000000000

说明

比赛场数 n=2。从后往前考虑：

• 第 2 场：p2=0.5，q2=0.5。参加期望打铁次数 0.5，不参加为 0，最优期望为 0.5。
• 第 1 场：p1=0.9，q1=1.0。若参加，期望打铁次数为 p1 + (1-q1)×0.5 + q1×0 = 0.9。若不参加，期望为 0.5。由于 0.9 > 0.5，应选择参加。 最终最大期望打铁次数为 0.9。

样例3

输入

3
0.2 0.1
0.3 1.0
0.4 0.5

输出

0.6000000000

说明

n=3。从后往前动态规划：

• 第 3 场：p3=0.4，q3=0.5，参加期望 0.4，不参加 0，取 0.4。
• 第 2 场：p2=0.3，q2=1.0，参加期望 0.3（因为参加后必然被禁赛，无法参加第 3 场），不参加期望 0.4，取 0.4。
• 第 1 场：p1=0.2，q1=0.1，参加期望 p1 + (1-q1)×0.4 + q1×0.4 = 0.2 + 0.9×0.4 + 0.1×0.4 = 0.6，不参加期望 0.4，取 0.6。 故最大期望打铁次数为 0.6。

样例4

输入

1
0.0 1.0

输出

0.0000000000

说明

唯一一场比赛成功打铁概率 p1=0，赛后禁赛概率 q1=1.0。无论是否参加，期望打铁次数均为 0。输出 0。