Software Licenses

Time limit1sMemory limit128 MB

Summary

Schedule n licenses, one per month, when license i costs P_i * R_i^t if bought after t months, and minimize total cost.

Level: Medium6 of 10
Topics: Greedy, Sorting, Math, Implementation
Solved: No attempts yet

Problem

You are launching a security company that must obtain licenses for $n$ different pieces of cryptographic software. Regulations let you obtain at most one license per month.

License $i$ currently sells for $P_i$ dollars, but every license appreciates along an exponential growth curve: the price of license $i$ grows by a factor of $R_i > 1$ each month. Concretely, if you wait $t$ months before buying license $i$ (so $t = 0$ means buying it in the first month at its current price), it costs $P_i \cdot R_i^{t}$ dollars.

Because you may buy at most one license per month, obtaining all $n$ licenses takes exactly $n$ months: you buy exactly one license in each of the months $t = 0, 1, \dots, n - 1$ . Decide which license to buy in each month so that the total amount paid is as small as possible, and report that minimum total cost.

Input

The first line contains a positive integer $n$ ( $1 \le n \le 100$ ), the number of licenses you must obtain.

Each of the next $n$ lines contains two numbers $P_i$ and $R_i$ ( $R_i > 1$ ): the current price of license $i$ and its monthly growth factor.

Output

Print a single line containing the minimum total cost, rounded to two decimal places.

Examples2

Example 1

Input

Expected output

1633.06

Example 2
Input
```
2
100 1.1
1000 1.05
```
Expected output
```
1110.00
```