体力与任务

时间限制：2.00s
内存限制：256.00MB

题目描述

你有 $n$ 个任务需要处理。任务 $i$ 有一个整数价值 $c_i$ 和一个难度 $p_i$ 。同时，你有一个初始体力值 $S = 1$ 。你必须按顺序从任务 $1$ 到任务 $n$ 处理这些任务。对于每个任务，你有两个选择：

放弃该任务：这种情况下，什么都不会发生。
完成该任务：这种情况下，你将获得 $S \cdot c_i$ 分。但是，完成任务后，体力值 $S$ 会下降为 $S \cdot (1 - \frac{p_i}{100})$ 。

你需要在处理完所有任务后，最大化你的总得分。

每个测试包含多个测试用例。

第一行包含一个整数 $t$ （ $1 \leq t \leq 10^3$ ），表示测试用例的数量。接下来是每个测试用例的描述。

每个测试用例的第一行包含一个整数 $n$ （ $1 \leq n \leq 10^5$ ），表示任务的数量。

接下来 $n$ 行，每行包含两个整数，分别表示 $c_i$ （ $1 \leq c_i \leq 100$ ）和 $p_i$ （ $0 \leq p_i \leq 100$ ）。

保证所有测试用例的 $n$ 之和不超过 $10^5$ 。

对于每个测试用例，输出一个实数——你能获得的最大可能得分。如果你的答案的绝对或相对误差不超过 $10^{-6}$ ，则被视为正确。

形式化地说，假设你的答案是 $a$ ，评委的答案是 $b$ 。当且仅当 $\frac{|a - b|}{\max(1, |b|)} \leq 10^{-6}$ 时，你的答案会被接受。

30.0000000000
29.0000000000

在第一个测试用例中，按顺序完成任务 $1$ 和任务 $2$ 是最优的，获得的分数为 $10 + 20 = 30$ 。

在第二个测试用例中，最优策略是完成任务 $1$ ，放弃任务 $2$ ，完成任务 $3$ 。在完成任务 $3$ 之前，你的体力值已经下降到 $1 - \frac{5}{100} = 0.95$ 。因此你的总收益为 $10 + 20 \cdot 0.95 = 29$ 分。