2208C. Stamina and Tasks

dp, greedy, math, https://codeforces.com/problemset/problem/2208/C

There are 𝑛 tasks for you. Task 𝑖 has an integer value of 𝑐𝑖 and a difficulty of 𝑝𝑖. Also, you have an initial stamina of 1, which is denoted as 𝑆. You should process the tasks from task 1 to task 𝑛. For each task, you have two choices.

• Give up the task. This way, nothing will happen.
• Complete the task. This way, you will gain 𝑆⋅𝑐𝑖 points. However, 𝑆 will drop to 𝑆⋅(1−𝑝𝑖100) after the task is completed.

You need to maximize your points after you finish the process.

Input

Each test contains multiple test cases. The first line contains the number of test cases 𝑡 (1≤𝑡≤10^3). The description of the test cases follows.

The first line of each test cases contain an integer 𝑛 (1≤𝑛≤10^5) denoting the number of tasks.

The following 𝑛 lines contain two integers each, denoting 𝑐𝑖 (1≤𝑐𝑖≤100) and 𝑝𝑖 (0≤𝑝𝑖≤100).

It is guaranteed that the sum of 𝑛 over all test cases does not exceed 10^5.

Output

For each test case, output a single real number — the maximum possible points you can get. Your answer is considered correct if its absolute or relative error does not exceed 10^−6.

Formally, let your answer be 𝑎, and the jury's answer be 𝑏. Your answer is accepted if and only if |𝑎−𝑏|max(1,|𝑏|)≤10^−6.

Example

input

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

output

30.0000000000
29.0000000000

Note

In the first test case, it's optimal to complete task 1 and 2 in order, gaining points of 10+20=30.

In the second test case, it's optimal to complete task 1, give up task 2, and complete task 3. Before completing task 3, your stamina has dropped to 1−5100=0.95. So your gain is 10+20⋅0.95=29 points in total.

【尹显齐 物院】水题。

假设 $S=1$ 时只选后面 $k$ 个题的最大收益为 $f(k)$ ，那么我们考虑新添加一个题 $(s_{k+1},p_{k+1})$，此时最大收益 $f(k+1)$ 满足

$$f(k+1)=max(f(k),s_{k+1}(1-\frac{p_{k+1}}{100})f(k))$$

递推即可。

for _ in range(int(input())):
    n = int(input())
    c,p = [],[]
    for i in range(n):
        ci,pi = map(int,input().split())
        c.append(ci)
        p.append(pi)
    ans = [0]*(n+1)
    for i in range(n-1,-1,-1):
        ans[i] = max(c[i]+(1-p[i]/100)*ans[i+1],ans[i+1])
    print(ans[0])