MINVEST - Investment Money

就是你有一笔钱，你要将这笔钱去投资债券，现在有$d$种债券，每种债券都有一个价值和年收益，债券的价值是$1000$的倍数，问你如何投资在$n$年后的获得最大收益。 【输入格式】 第一个为一个整数$M$，表示有$M$组数据。 每组数据第一行有两个整数，表示初始资金(不超过$50000$)和年数$n$。 每组数据第二行为一个整数d($1 le d \le 10$)，表示债券种类。 随后$d$行每行有两个整数，表示该债券的价值和年收益。年收益不会超过债券价值的$10%$。 **所有数据不超过整型取值范围。** 【输出格式】 每组数据，输出n年后获得的最大收益。 【输入样例】 ``` 1 10000 4 2 4000 400 3000 250 ``` 【输出样例】 ``` 14050 ```

[English](/problems/MTEMP/en/) [Vietnamese](/problems/MTEMP/vn/)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. John did not need that much money for the moment. But he realized that it would be a good idea to store this capital in a safe place, and have it grow until he decided to retire. The bank convinced him that a certain kind of bond was interesting for him. This kind of bond has a fixed value, and gives a fixed amount of yearly interest, payed to the owner at the end of each year. ``` ``` The bond has no fixed term. Bonds are available in different sizes. The larger ones usually give a better interest. Soon John realized that the optimal set of bonds to buy was not trivial to figure out. Moreover, after a few years his capital would have grown, and the schedule had to be re-evaluated. Assume the following bonds are available: ``` Value Annual interest 4000 400 3000 250 ``` With a capital of 10 000$ one could buy two bonds of 4000$, giving a yearly interest of 800$. Buying two bonds of 3000$, and one of 4000$ is a better idea, as it gives a yearly interest of e900. After two years the capital has grown to 11800$, and it makes sense to sell a 3000$ one and buy a 4000$ one, so the annual interest grows to 1050$. This iswhere this story grows unlikely: the bank does not charge for buying and selling bonds. Next year the total sum is 12850$, which allows for three times 4000$, giving a yearly interest of 1200$. Here is your problem: given an amount to begin with, a number of years, and a set of bonds with their values and interests, find out how big the amount may grow in the given period, using the best schedule for buying and selling bonds. ``` Input ``` ``` The first line contains a single positive integer N which is the number of test cases. The first line of a test case contains two positive integers: the amount to start with (at most 1000 000$), and the number of years the capital may grow (at most 40). The following line contains a single number: the number d (1 ```