Bond Investment Strategy

John has an initial asset of \(S\) dollars and can invest in one or more types of bonds. Each bond type \(i\) is characterized by:

• An investment cost \(c_i\) dollars, and
• An annual interest yield \(r_i\) dollars.

The investment process lasts for \(n\) years. In each year, John is allowed to reallocate his entire asset as follows:

1. Using his current asset \(A\), he can purchase any number of bonds of any type (each bond must be purchased as a whole unit) such that the total investment does not exceed \(A\).
2. The money that is not invested does not earn any interest.
3. At the end of the year, he receives interest equal to the sum of the yields from the bonds he holds.
4. Then, his asset for the next year becomes \(A + \text{(total interest)}\). He can then sell his bonds and reinvest his entire asset for the next year.

Your task is to help John determine the maximum asset value he can achieve after \(n\) years.

Example:

Suppose there are 2 types of bonds:

1. Bond 1: Investment cost \(4000\) dollars and annual interest \(400\) dollars.
2. Bond 2: Investment cost \(3000\) dollars and annual interest \(250\) dollars.

If John starts with \(10000\) dollars and invests optimally, one possible sequence of actions is:

• Year 1: Purchase 1 unit of Bond 1 and 2 units of Bond 2 (total cost \(4000 + 2\times3000 = 10000\)). The total annual interest is \(400 + 2\times250 = 900\) dollars. End-of-year asset becomes \(10000 + 900 = 10900\).
• Year 2: Reinvest with the new asset to similarly maximize the interest. (Detailed decisions may vary.)
• After 4 years, the maximum asset attainable following an optimal strategy is \(14050\) dollars.

Note: The above example is only illustrative. In the actual problem, you are given \(m\) types of bonds along with their costs and yields, the number of years \(n\), and the initial asset \(S\). You must compute the maximum asset value achievable after \(n\) years by re-investing optimally each year.

inputFormat

The input consists of several lines:

1. The first line contains three integers \(m\), \(n\), and \(S\) where:
• \(m\): the number of bond types,
• \(n\): the number of years,
• \(S\): the initial asset (in dollars).
2. Each of the next \(m\) lines contains two integers \(c_i\) and \(r_i\), representing the investment cost and the annual interest yield of the \(i\)-th bond respectively.

You may assume that all numbers are positive integers.

outputFormat

Output a single integer, which is the maximum asset value that John can have after \(n\) years of optimal investment.

sample

2 4 10000
4000 400
3000 250

14050