有 $$$n$$$ 任务等着你。任务 $$$i$$$ 的整数值为 $$$c_i$$$,难度为 $$$p_i$$$。另外,你的初始耐力为$$$1$$$,表示为$$$S$$$。您应该处理从任务 $$$1$$$ 到任务 $$$n$$$ 的任务。对于每项任务,您有两种选择。
- 放弃任务。这样,就不会发生什么事情了。
- 完成任务。这样,您将获得 $$$S\cdot c_i$$$ 积分。然而,$$$S$$$ 将下降到 $$$S\cdot (1-\frac{p_i}{100})$$$ 之后 任务已完成。
完成该过程后,您需要最大化您的积分。
输入
每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^3$$$)。测试用例的描述如下。
每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1\le n\le10^5$$$) 表示任务数。
以下 $$$n$$$ 行每行包含两个整数,表示 $$$c_i$$$ ($$$1\le c_i\le 100$$$) 和 $$$p_i$$$ ($$$0\le p_i\le 100$$$)。
保证所有测试用例的$$$n$$$总和不超过$$$10^5$$$。
输出
对于每个测试用例,输出一个实数 - 您可以获得的最大可能分数。如果您的答案的绝对或相对误差不超过 $$$10^{-6}$$$,则视为正确。
正式来说,让您的答案为 $$$a$$$,陪审团的答案为 $$$b$$$。当且仅当 $$$\frac{|a−b|}{\max(1,|b|)}\le 10^{-6}$$$ 时,您的答案才会被接受。
示例
输入复制
2210 020 5310 510 8020 5
输出复制
30.000000000029.0000000000
注意
在第一个测试用例中,最好按顺序完成任务$$$1$$$ 和$$$2$$$,获得$$$10+20=30$$$ 积分。
在第二个测试用例中,最佳完成任务$$$1$$$,放弃任务$$$2$$$,并完成任务$$$3$$$。在完成任务 $$$3$$$ 之前,你的耐力已降至 $$$1-\frac{5}{100}=0.95$$$。所以你总共获得$$$10+20\cdot 0.95=29$$$点。