有一笔钱去投资债券,现在有d种债券,每种债券都有一个价值和年收益,债券的价值是1 000的倍数,问如何投资,在n年后获得最大收益。
例如初始资金为10 000,有两种债券,一种价值4 000,年收益为400,一种价值3 000,年收益为250。如果买两张价值4 000的债券,年收益为800,但显然买两张价值3 000的债券和一张价值4 000的债券,年收益为900是更好的选择。这样两年后资金已经涨到1 1800。此时如果出售一张价值3 000的债券,再买进一张价值4 000的债券,年收益将涨到1 050。
第一个为一个整数T,表示有T组数据。
每组数据第一行有两个整数,表示初始资金(不超过1 000 000)和年数n(不超过40)。
每组数据第二行为一个整数d(1≤d≤10),表示债券种类。
随后d行每行有两个整数,表示该债券的价值和年收益。年收益不会超过债券价值的10\%。
所有数据不超过整型取值范围。
每组数据,输出n年后获得的最大收益。
1 10000 4 2 4000 400 3000 250
14050