Problem G
Good Coalition
The Dutch political system is in turmoil. There have been six coalition governments in the past fourteen years, all of which have fallen before completing their term in office. Recently there have been elections (again), the outcome of which has been described as “impossible” by several political commentators. The only bright spot in this bleak situation is that they have appointed you as the “informateur”. As the informateur it is your task to find a suitable coalition.
Being the rational person you are, you have decided the first negotiation attempt should be started between the parties forming the most stable coalition. A coalition is formed by a set of parties having won a strict majority of seats in the election (i.e. at least 76 seats out of a total of 150). The most stable coalition is one that has the highest chance of completing its term in office. A coalition falls (and new elections must be held) if a single party leaves the coalition. The probability of a coalition completing their term is estimated by the product of the probabilities of each party in the coalition completing their term. This probability is in turn based on historical data.
Find the best coalition and save the Netherlands from becoming a banana republic!
Input
On the first line one positive number: the number of test cases, at most 100. After that per test case:
-
one line with an integer $n$ ($1 \leq n \leq 150$), the number of political parties that have won at least one seat in the election.
-
$n$ lines, each with two space-separated integers $s_ i$ and $p_ i$ ($1 \leq s_ i \leq 150$ and $1 \leq p_ i \leq 100$): the number of seats won by the $i$-th party and the probability (expressed as a percentage) that the $i$-th party will complete its term in office, respectively.
Note that there are exactly 150 seats divided among all parties $\left(\sum \limits _{i=1}^ n s_ i = 150\right)$.
Output
Per test case:
-
one line with a floating point number: the probability (expressed as a percentage) of the most stable coalition sitting out their term in office.
This number should be accurate up to $10^{-6}$ relative or absolute precision.
| Sample Input 1 | Sample Output 1 |
|---|---|
1 4 35 80 25 70 60 60 30 90 |
54.0 |
