시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 0 0 0 0.000%


John never knew he had a grand-uncle, until he received the notary‘s letter. He learned that his late grand-uncle had gathered a lot of money, somewhere in South-America, and that John was the only inheritor.



Assume the following bonds are available:

Value Annual interest
4000 400
3000 250

With a capital of e 10 000 one could buy two bonds of e 4 000, giving a yearly interest of e 800. Buying two bonds of e 3 000, and one of e 4 000 is a better idea, as it gives a yearly interest of e 900. After two years the capital has grown to e 11 800, and it makes sense to sell a e 3 000 one and buy a e 4 000 one, so the annual interest grows to e 1 050. This is where this story grows unlikely: the bank does not charge for buying and selling bonds. Next year the total sum is e 12 850, which allows for three times e 4 000, giving a yearly interest of e 1 200.




The first line of a test case contains two positive integers: the amount to start with (at most e 1 000 000), and the number of years the capital may grow (at most 40).

The following line contains a single number: the number d (1 ≤ d ≤ 10) of available bonds.

The next d lines each contain the description of a bond. The description of a bond consists of two positive integers: the value of the bond, and the yearly interest for that bond. The value of a bond is always a multiple of e 1 000. The interest of a bond is never more than 10% of its value.



예제 입력

10000 4
4000 400
3000 250

예제 출력