题目描述

有 $n$ 个任务需要处理。第 $i$ 个任务有一个整数值 $c_i$ 和一个难度值 $p_i$。小明一开始的体力值为 $1$，记为 $S$。小明需要按照从第 $1$ 个到第 $n$ 个的顺序处理这些任务。

对于每个任务，小明有两种选择：

1. 放弃这个任务，这样不会发生任何事情。
2. 完成这个任务，这样小明会获得 $S \cdot c_i$ 分，但是完成后体力值 $S$ 会变成 $S \cdot (1 - \frac{p_i}{100})$。

小明需要让处理完所有任务后的总得分尽可能大，求出这个最大的得分。

输入格式

输入包含多组测试用例。 第一行是测试用例的数量 $t$（$1 \le t \le 10^3$）。 每组测试用例的第一行是一个整数 $n$（$1 \le n \le 10^5$），表示任务的数量。 接下来的 $n$ 行，每行有两个整数，分别表示第 $i$ 个任务的 $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}$ 时，答案被接受。

2
2
10 0
20 5
3
10 5
10 80
20 5

30.0000000000
29.0000000000

数据规模与约定

对于 $100\%$ 的数据，满足 $1 \le t \le 10^3$，$1 \le n \le 10^5$，$1 \le c_i \le 100$，$0 \le p_i \le 100$，所有测试用例的 $n$ 之和不超过 $10^5$。

来源

https://codeforces.com/contest/2208/problem/C