Migrated from Lutece 2699 偷税の卷王

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

众所周知，guapisolo 喜欢内卷，他通过做题来获得愉悦度。guapisolo 现在有 $n$ 道题目，现在把这些题目排成一行，已知从左往右数第 $i$ 道题目的价值是一个整数 $a_{i}$，他 AC 这道题的概率是一个在 $[0,1]$ 之间的小数 $p_{i}$。

guapisolo 按从左到右依次做题，每道题只做一次。如果 guapisolo AC 了第 $i$ 道题，那么他会很开心，愉悦度增加 $a_{i}$，并且 guapisolo 会把这道题纳入收藏。如果 guapisolo 没有 AC 第 $i$ 道题，那么他会被自己菜哭，愉悦度减少 $a_{i}$，然后 guapisolo 会找点乐子排遣忧愁，把之前收藏的题目全部复习一遍，愉悦度增加已收藏题目的价值之和。

guapisolo 觉得目前的训练方案可能不够优秀。为了达到最佳的训练效果，guapisolo 可以任意重排题目的顺序（也可以保持原有顺序不重排），但不能添加或删除任何题目。

现在 guapisolo 开始好奇，如何重排题目顺序，能使得愉悦度的期望最大？你只需要输出这个最大的期望值。

Input

第一行一个整数 $n\ (1\le n\le 50)$，代表题目数量。

接下来 $n$ 行，每行一个整数和一个小数 $a_i,p_i\ (0\le a_{i}\le 1000,0\le p_{i}\le 1)$，分别代表第 $i$ 道题目的价值以及 AC 这道题的概率。保证 $p_i$ 均保留小数点后 $7$ 位。

Output

输出一个小数表示最大期望值，保留小数点后六位。

Samples

2
1 0.5000000
2 0.5000000

0.500000

4
3 0.4500000
2 0.3000000
5 0.4000000
4 0.9000000

11.205000

Note

为了方便说明，我们把重排前的题目按从左往右顺序从 $1$ 标到 $n$ ，重排后题目改变，标号不变。

样例 1：

如果重排后的题目编号是 $[1,2]$。

先不考虑复习带来的贡献，AC 第一道题的概率是 $0.5$，期望贡献是 $0.5\times 1+(1-0.5)\times(-1)=0$，AC 第二道题的概率也是 $0.5$，期望贡献是 $0.5\times 2+(1-0.5)\times(-2)=0$。

再加上复习的贡献，此时 AC 第一道题且没有 AC 第二道题，$(1-0.5)\times 0.5\times 1=0.25$，总期望贡献是 $0.25$。

如果重排后的题目编号是 $[2,1]$。

如果不考虑复习带来的贡献，AC 第一道题和 AC 第二道题的期望贡献不变。

复习的贡献改变，变成 $(1-0.5)\times 0.5\times 2=0.5$，总期望贡献是 $0.5$。

经过计算，重排成 $[2,1]$ 更优。

样例 2：

重排后的题目编号是 $[4,3,1,2]$。

建议使用 $\texttt{double}$ 类型来提高小数精度。

（guapisolo: 题面 idea 来自 NamelessOIer。不会真有人喜欢内卷吧？）

Resources

电子科技大学第十二届 ACM 趣味程序设计竞赛