The Ohgas are a prestigious family based on Hachioji. The head of the family, Mr. Nemochi Ohga, a famous wealthy man, wishes to increase his fortune by depositing his money to an operation company. You are asked to help Mr. Ohga maximize his profit by operating the given money during a specified period.
From a given list of possible operations, you choose an operation to deposit the given fund to. You commit on the single operation throughout the period and deposit all the fund to it. Each operation specifies an annual interest rate, whether the interest is simple or compound, and an annual operation charge. An annual operation charge is a constant not depending on the balance of the fund. The amount of interest is calculated at the end of every year, by multiplying the balance of the fund under operation by the annual interest rate, and then rounding off its fractional part. For compound interest, it is added to the balance of the fund under operation, and thus becomes a subject of interest for the following years. For simple interest, on the other hand, it is saved somewhere else and does not enter the balance of the fund under operation (i.e. it is not a subject of interest in the following years). An operation charge is then subtracted from the balance of the fund under operation. You may assume here that you can always pay the operation charge (i.e. the balance of the fund under operation is never less than the operation charge). The amount of money you obtain after the specified years of operation is called ``the final amount of fund.'' For simple interest, it is the sum of the balance of the fund under operation at the end of the final year, plus the amount of interest accumulated throughout the period. For compound interest, it is simply the balance of the fund under operation at the end of the final year.
Operation companies use C, C++, Java, etc., to perform their calculations, so they pay a special attention to their interest rates. That is, in these companies, an interest rate is always an integral multiple of 0.0001220703125 and between 0.0001220703125 and 0.125 (inclusive). 0.0001220703125 is a decimal representation of 1/8192. Thus, interest rates' being its multiples means that they can be represented with no errors under the double-precision binary representation of floating-point numbers.
For example, if you operate 1000000 JPY for five years with an annual, compound interest rate of 0.03125 (3.125 %) and an annual operation charge of 3000 JPY, the balance changes as follows.
The balance of the fund under operation(at the beginning of year) | Interest | The balance of the fund under operation (at the end of year) |
A | B = A × 0.03125 (and rounding off fractions) | A + B - 3000 |
1000000 | 31250 | 1028250 |
1028250 | 32132 | 1057382 |
1057382 | 33043 | 1087425 |
1087425 | 33982 | 1118407 |
1118407 | 34950 | 1150357 |
After the five years of operation, the final amount of fund is 1150357 JPY.
If the interest is simple with all other parameters being equal, it looks like:
The balance of the fund under operation (at the beginning of year) | Interest | The balance of the fund under operation (at the end of year) | Cumulative interest |
A | B = A × 0.03125 (and rounding off fractions) | A - 3000 | |
1000000 | 31250 | 997000 | 31250 |
997000 | 31156 | 994000 | 62406 |
994000 | 31062 | 991000 | 93468 |
991000 | 30968 | 988000 | 124436 |
988000 | 30875 | 985000 | 155311 |
In this case the final amount of fund is the total of the fund under operation, 985000 JPY, and the cumulative interests, 155311 JPY, which is 1140311 JPY.