Ohga's Fortune

The Ohga family is a distinguished household. The head of the family, Mr. Nemochi Ohga, a famous wealthy man, wishes to grow his fortune by depositing his money with an operation (investment) company. Help Mr. Ohga maximize his profit by operating the given money for a specified period.

From a list of possible operations you choose exactly one, deposit the entire fund into it, and commit to that single operation for the whole period. Each operation specifies:

• an annual interest rate,
• whether the interest is simple or compound, and
• an annual operation charge — a constant that does not depend on the balance.

At the end of every year the interest is computed by multiplying the current balance of the fund under operation by the annual interest rate and then discarding the fractional part (rounding down).

• For compound interest, the interest is added to the balance under operation, so it earns interest in later years.
• For simple interest, the interest is set aside elsewhere and does not enter the balance under operation, so it does not earn interest in later years.

After the interest step the annual operation charge is subtracted from the balance under operation. You may assume the charge can always be paid (the balance under operation is never less than the charge).

The money obtained after the specified number of years is called the final amount of fund:

• For simple interest, it is the balance under operation at the end of the final year plus the total interest accumulated over the whole period.
• For compound interest, it is simply the balance under operation at the end of the final year.

Operation companies pay special attention to their interest rates: a rate is always an integral multiple of 0.0001220703125 and lies between 0.0001220703125 and 0.125 inclusive. Since 0.0001220703125 equals 1/8192, every such rate can be represented exactly in double-precision binary floating point.

For example, operating 1000000 JPY for five years at an annual compound rate of 0.03125 (3.125%) with an annual operation charge of 3000 JPY, the balance evolves as follows.

After five years the final amount of fund is 1150357 JPY.

If instead the interest is simple with all other parameters equal, it evolves as follows.

Here the final amount of fund is the ending balance under operation, 985000 JPY, plus the cumulative interest, 155311 JPY, for a total of 1140311 JPY.

The input consists of several datasets. The whole input has the form:

m
dataset 1
dataset 2
...
dataset m

where m is the number of datasets (m no more than 100). Each dataset has the form:

initial-fund
years
n
operation 1
operation 2
...
operation n

• initial-fund — the initial amount of the fund, a positive integer no more than 100000000.
• years — the number of years of operation, a positive integer no more than 10.
• n — the number of available operations, a positive integer no more than 100.

Each operation is given on one line as:

simple-or-compound annual-interest-rate annual-operation-charge

where simple-or-compound is a single character (0 for simple interest, 1 for compound interest), annual-interest-rate is a decimal fraction that is an integral multiple of 1/8192, and annual-operation-charge is an integer not exceeding 100000.

For each dataset, print a single line containing one decimal integer: the final amount of fund for the best operation, i.e. the operation that yields the maximum final amount among all available operations. The line must contain nothing but this number.

You may assume the final amount never exceeds 1000000000, and that at least one operation yields a final amount no less than the initial fund.