For a website, you need to design an algorithm to decrease the total access cost. The website is used to search some items. The search items change time to time. In order to have a faster search you want the most frequent items to be accessed first (the most frequent items to be usually at the top positions). The total access cost of a BST is:

Question: Write a program that takes names and probabilities of n items, then it calculates the cost of BST configuration such that it complies the BST property and has the minimum access cost (the item on the left is smaller and the item on the right is greater than the root).

Input specification: You will be given an integer in the beginning: the number of items (n). In the following n-lines, you will be given the names and probabilities of n items where where 0 ≤ n ≤ 200

Output specification:
Show one floating point number with three digits precision.

Explanation:
When "or" is at the top, its access cost will be 0.2 (probability) * 1 (depth+1) . Then, the minimum total access cost is
(0.22 * 3) + (0.18 * 2) + (0.08 * 3) + (0.02 * 4) + (0.2 * 1) + (0.05 * 3) + (0.25 * 2) = 2.19