5650번 - Software Licenses 다국어

You are starting a security company that needs to obtain licenses for n different pieces of cryptographic software. Due to regulations, you can only obtain these licenses at the rate of at most one per month.

Currently the license i is selling for a price of Pi dollars. However, they are all becoming more expensive according to exponential growth curves: in particular, the cost of license i increases by a factor of Ri > 1. This means that if license i is purchased t months from now, it will cost P_i * (R_i)^t dollars.

Given a set of n license prices and their growth factors, you have to plan the purchase of these licenses within n months in order to minimize the total cost.

For example, you need to buy licenses A, B, C, D. Their prices and factors are the following. P_A = 200, R_A = 1.01, P_B = 300, R_B = 1.12, P_C = 400, R_C = 1.05, P_D = 650, R_D = 1.10

You can buy all needed licenses within 4 months. To obtain the minimum cost of 1,633.06 dollars you have to purchase D in the first month (with its initial price), then B in the second month, and then C in the third month and A in the last month. 

The first line contains a positive integer n 1( ≤ n ≤ 100) indicating the number of licenses you need. The next n lines contain 2 numbers: P_j and R_j in each line.

The output is the minimum cost that you have to pay. The number must be rounded to 2 decimal places.