# Problem C

Password Hacking

You have done a lot of hacking using such lists, and you have a good idea of how likely each password in the list is the correct one (you are very surprised by the number of people using “123456” as their passwords). You have a new account to hack, and you have decided to try each of the passwords in the list one at a time, until the correct one is found. You are absolutely sure that the account you want to hack uses a password in the given list.

What is the expected number of attempts to find the correct passwords, assuming that you try these passwords in the optimal order?

## Input

The first line of input contains a positive integer $N$, the number of passwords in the list. Each of the next $N$ lines gives the password, followed by a space, followed by the probability that the password is the correct one. Each password consists only of alphanumeric characters and is $1$ to $12$ characters long. Each probability is a real number with $4$ decimal places. You may assume that there are at most $500$ passwords in the list, and that the sum of all probabilities equals $1$. No two passwords in the list are the same.

## Output

Output on a single line the expected number of attempts to find the correct passwords using the optimal order. Answers within $10^{-4}$ of the correct answer will be accepted.

Sample Input 1 | Sample Output 1 |
---|---|

2 123456 0.6666 qwerty 0.3334 |
1.3334 |

Sample Input 2 | Sample Output 2 |
---|---|

3 qwerty 0.5432 123456 0.3334 password 0.1234 |
1.5802 |