解题思路

1. 设 $dp_i$ 表示第 $i$ 周开始时，小 $C$ 没有被禁赛、可以自由选择是否参加第 $i$ 场比赛时，从第 $i$ 周到赛季结束能获得的最大期望打铁次数。

2. 如果跳过第 $i$ 场比赛，则不会产生收益，也不会触发禁赛，期望为 $dp_{i+1}$。

3. 如果参加第 $i$ 场比赛，则本场贡献期望 $p_i$。赛后有 $1-q_i$ 的概率下周仍可参加，对应 $dp_{i+1}$；有 $q_i$ 的概率第 $i+1$ 周被禁赛，禁令在该周结束后解除，对应 $dp_{i+2}$。

4. 因此转移为：

   $$dp_i=\max(dp_{i+1},\ p_i+(1-q_i)dp_{i+1}+q_i dp_{i+2})$$

题目内容

铁制品工艺练习赛（$Iron$ $Craft$ $Practising$ $Contest$, $ICPC$）赛季即将开始。在接下来的连续 $n$ 周内，每周将在某个城市举行一次比赛。

根据经验，小 $C$ 在第 $i$ 场比赛中成功打铁的概率为 $p_i$。

如果小 $C$ 参加比赛，则在赛后有 $q_i$ 的概率被教练禁止参加下一周（即第 $i+1$ 周）的比赛。无论他是否参加第 $i+1$ 周的比赛，此禁令都会在第 $i+1$ 周结束后自动解除。

小 $C$ 可以选择任意场比赛参加。小 $C$ 希望最大化本赛季打铁次数的期望值。

【名词解释】 期望值：期望值是概率论中的一个概念，指随机变量在多次试验中的平均结果。例如，投掷一枚均匀硬币，正面向上得分 $1$，反面向上得分 $0$，其期望值为 $0.5$。

输入描述

第一行输入一个整数 $n\ (1 \le n \le 10^6)$，表示比赛场次数。 接下来 $n$ 行，每行输入两个实数 $p_i, q_i\ (0 \le p_i, q_i \le 1)$，其中：

• $p_i$ 表示第 $i$ 场比赛成功打铁的概率；
• $q_i$ 表示第 $i$ 场比赛后被禁止参加下一场比赛的概率。

输出描述

输出一个实数，表示小 $C$ 本赛季打铁次数的最大期望值。

由于浮点数计算可能产生误差，当误差的量级不超过 $10^{-6}$ 时，你的答案将被认为是正确。具体来说，设你的答案为 $a$，标准答案为 $b$，当且仅当 $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$ 时，答案被接受。

样例1

输入

2
0.5 0.5
0.5 0.0

输出

0.75

说明

• 第 $1$ 场比赛：成功概率 $0.5$，禁赛概率 $0.5$；
• 在第 $1$ 场之后，有 $0.5$ 的概率被禁赛，此时无法参加第 $2$ 场；有 $0.5$ 的概率可继续参加；
• 如果继续参加，则在第 $2$ 场比赛中成功概率为 $0.5$；
• 因此期望值为 $0.5 + 0.5 \times 0.5 = 0.75$。

样例2

输入

5
1.0 0.0
1.0 0.0
1.0 0.0
1.0 0.0
1.0 0.0

输出

5

说明

在该样例中，每场比赛都必定成功且不会被禁赛，因此总期望打铁次数为 $5$。