题目内容

小L计划在接下来的 $n$ 天里参加每日挑战，每天都有一次独立的挑战机会。第 $i$ 天挑战成功的概率为 $p_i$，成功即可获得 $1$ 分；但若小L在第 $i$ 天参与了挑战，则当天结束后有 $q_i$ 的概率因体力透支而被强制休息一天，即第 $i+1$ 天不能参与挑战。无论第 $i+1$ 天是否被禁止参与，该休息指令都会在第 $i+1$ 天结束时自动解除。小L可以自由决定每一天是否参与挑战（若某一天被强制休息，则当天自然无法参与）。他想最大化整个 $n$ 天内的期望总分。请你计算这个最大期望值。

天数 $n$ 不超过 $10^6$，所有的概率 $p_i, q_i$ 均为 $0$ 到 $1$ 之间的实数。

输入描述

第一行包含一个整数 $n$ $(1 \le n \le 10^6)$。接下来的 $n$ 行，每行包含两个用空格分隔的实数 $p_i$ 和 $q_i$ $(0 \le p_i, q_i \le 1)$，分别表示第 $i$ 天的成功概率和强制休息概率。

输出描述

输出一个实数，表示最大期望总分。当输出与标准答案的相对或绝对误差不超过 $10^{-6}$ 时视为正确。具体地，若你的输出为 $a$，标准答案为 $b$，则需满足 $\frac{|a-b|}{\max(1,|b|)} \le 10^{-6}$。