408824: GYM103329 I Typing Contest

Teacher Docriz is planning to select some students in his class for a typing contest.

There are $$$n$$$ students in the class. The $$$i$$$-th classmate's initial typing speed is $$$s_i$$$ and the typing noise is $$$f_i$$$. However, when several students are selected to compete, their total typing speed is not the sum of everyone's initial typing speed, because the noise each person makes affects others.

Specifically, if students $$$1, 2, 3, \ldots, k$$$ form a team, the actual typing speed of student $$$1$$$ is $$$s_1 \cdot (1 - f_1 f_2 - f_1 f_3 - \ldots - f_1 f_k)$$$, the actual typing speed of student $$$2$$$ is $$$s_2 \cdot (1 - f_2 f_1 - f_2 f_3 - \ldots - f_2 f_k)$$$, and so on.

Teacher Docriz wants to form a team so that the total typing speed is as large as possible. Please help him calculate the maximum typing speed he could possibly achieve.

The first line contains an integer $$$T$$$ ($$$1 \leq T \leq 2000$$$), the number of test cases. Then $$$T$$$ test cases follow.

The first line of each test case contains a single integer $$$n$$$ ($$$1 \leq n \leq 100$$$), the number of students.

Then $$$n$$$ lines follow, each line contains two numbers $$$s_i$$$, $$$f_i$$$ ($$$1 \leq s_i \leq 10^{12}$$$, $$$0 \leq f_i \leq 1$$$), where $$$s_i$$$ is an integer and $$$f_i$$$ is a real number with exactly two decimal places.

It is guaranteed that $$$\sum n \leq 2000$$$.

For each test case, output a line with a single real number: the maximum typing speed that teacher Docriz can achieve. Keep your answers to exactly $$$9$$$ decimal places after the decimal point.

It is guaranteed that the answer is absolutely precise when $$$9$$$ decimal places are used, so only the answers that coincide with the model solution are accepted, so please ensure the accuracy of your output.

4
3
10 0.00
11 0.00
12 0.00
3
10 1.00
11 1.00
12 1.00
3
10 0.50
11 0.50
12 0.50
3
10 0.33
11 0.21
12 0.92

33.000000000
12.000000000
17.250000000
20.421900000