题目描述

设有$\red{n }$个程序$\red{\{1,2,…, n \}}$要存放在长度为L的磁带上。程序$\red{i}$存放在磁带上的长度是$\red{l_i，1<=i<=n}$。这$\red{n }$个程序的读取概率分别是$\red{p_1 ,p_2 …p_n}$，且$\red{\displaystyle\sum_{i=1}^{n}p_i=1}$ 。如果将这$\red{n }$个程序按$\red{i_1 ,i_2 …i_n}$的次序存放，则读取程序所$\red{i_r}$需的时间 $\red{t_r=c\displaystyle\sum_{k=1}^{r}p_{ik}l_{ik}}$ 。这$\red{n }$个程序的平均读取时间为 $\red{\displaystyle\sum_{i=1}^{n}t_r}$ 磁带最优存储问题要求确定这$\red{n}$ 个程序在磁带上的一个存储次序，使平均读取时间达到最小。试设计一个解此问题的算法,并分析算法的正确性和计算复杂性。

编程任务： 对于给定的$\red{n}$个程序存放在磁带上的长度和读取概率，编程计算$\red{n}$个程序的最优存储方案。

输入格式

第一行是正整数$\red{n}$，表示文件个数。接下来的$\red{n}$行中，每行有$\red{2}$ 个正整数$\red{a}$ 和$\red{b}$，分别表示程序存放在磁带上的长度和读取概率。实际上第$\red{k}$个程序的读取概率 $\red{a_k/\displaystyle\sum_{i=1}^{n}a_i}$ 。对所有输入均假定$\red{c=1}$。

输出格式

计算出最小平均读取时间（保留小数点后一位）。

样例

输入样例

5
71 872
46 452
9 265
73 120
35 85

输出样例

85.6