文理学院程序设计在线练习


压岁钱

Time Limit: 3 Second(s)    Memory Limit: 32 MB

Total Submission(s): 74   Accepted Submission(s): 22
Problem Description

今年春节,小明太高兴了,因为他得到了许多压岁钱,那个不是个小数目。虽然压岁钱可以自由支配,但小明毕竟还在上小学,显然用不了这些钱。
小明知道将钱存入银行可以获得利息,使资金增值。可是由于当前的金融危机,银行的利率相当低,好在银行提供了许多基金投资的机会。
购买基金和存钱不同,必须整份进行购买,当然,为了控制投资风险也为了让更多的基民可以购买基金,每种基金均设有一个投资上限(或者说投资总额)。
当然,不同基金的年收益是不一样的,这也是选择基金的重要参考依据。

假设基金是以年度为基本时间单位,具有固定的回报,且以年度为基本单位进行结算。每年均可以重新选择新的投资方案。

例如,银行提供了如下2类基金:
------------------------------------------------------------------------------------
序号 每份单位基金(元) 年回报(元)  投资份额上限(份)
1   4000       600      1
2   5000       550      2
------------------------------------------------------------------------------------

显然,不同的投资方式可能有不同的收益。例如:初值9000元,年限2年。相对较合理的投资方案为(注意基金1的购买上限):

方案1:
第1年:4000 + 5000,到期后总资产:9000+600+550=10150
第2年:4000 + 5000,到期后总资产:10150+600+550=11300

方案2:
第1年:4000 + 5000,到期后总资产:9000+600+550=10150
第2年:5000 + 5000,到期后总资产:10150+550+550=11250

在上述列举的2种投资方案中,方案1优于方案2。

现在的问题:给定初始资金M和投资年限N,请你计算N年后的最大总资产。

Input

输入数据首先包含一个整数T(1<=T<=50),表示测试实例的个数,然后是T组测试数据。

每组测试的第一行是3个整数M, N, K(100<=M<=10000,1<=N<=10,1<=K<=10),分别代表初始金额,投资年限,和基金种类。
然后是 K 行数据,每行3个整数Ai,Bi,Ci。分别代表第i种基金的单价、年投资回报以及该基金的投资份额上限。
其中 100<=Ai<=10000, 1<=Ci<=20, 假设基金的回报比率在0%~20%之间

Output

对每一个测试实例,输出投资N年后最大价值。

Sample Input
1
9000 2 2
4000 600 1
5000 550 2
Sample Output
11300
Author

flx

Source

zscas第三届程序设计竞赛