{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"约翰从未意识到他有一个曾祖父,直到收到公证书的信。他得知他已故的曾祖父在南美某处积累了大量财富,而约翰是唯一的继承人。\u003cbr\u003e约翰目前并不需要那么多的钱。但他意识到将这笔资本存放在一个安全的地方,并让其增值直到他决定退休是个好主意。银行说服他某种类型的债券对他很有吸引力。\u003cbr\u003e这种债券具有固定价值,并且每年末向所有者支付固定金额的年度利息。债券没有固定期限。不同规模的债券可供选择。通常较大的债券利息更高。很快约翰意识到买入的最佳债券组合并不容易确定。此外,几年后他的资本将会增长,计划需要重新评估。\u003cbr\u003e假设以下债券可供选择:\u003cbr\u003e\u003ccenter\u003e\u003ctable border\u003d\"1\"\u003e\u003ctbody\u003e\u003ctr align\u003d\"center\"\u003e\u003ctd\u003e价值\u003c/td\u003e\u003ctd\u003e年度\u003cbr\u003e利息\u003c/td\u003e\u003c/tr\u003e\u003ctr align\u003d\"right\"\u003e\u003ctd\u003e4000\u003cbr\u003e3000\u003c/td\u003e\u003ctd\u003e400\u003cbr\u003e250\u003c/td\u003e\u003c/tr\u003e\u003c/tbody\u003e\u003c/table\u003e\u003c/center\u003e\u003cbr\u003e拥有 10,000 欧元的资本可以购买两张 800 欧元的债券。购买两张 4,000 欧元的债券是更好的选择,因为它提供了 11,800 欧元的年度利息,有意义的是卖掉一张 4,000 欧元的债券,这样年度利息增长到 12,850 欧元,这样可以三次 1,200 欧元。\u003cbr\u003e这是你的问题:给定一个初始金额、一个年数,以及一组带有其价值和利息的债券,找出在给定期间内资本可能增长多少,使用最佳的债券购买和出售计划。"}},{"title":"输入","value":{"format":"HTML","content":"第一行包含一个正整数 N,表示测试用例的数量。接下来是测试用例。\u003cbr\u003e每个测试用例的第一行包含两个正整数:初始金额(最多 1,000,000 欧元)和资本增长的年数(最多 40 年)。\u003cbr\u003e接下来一行包含一个数字:可用债券的数量 d(1 \u003c\u003d d \u003c\u003d 10)。\u003cbr\u003e接下来的 d 行每行包含一个债券的描述。债券的描述包括两个正整数:债券的价值和该债券的年度利息。债券的价值始终是 1,000 欧元的倍数。债券的利息永远不会超过其价值的 10%。"}},{"title":"输出","value":{"format":"HTML","content":"对于每个测试用例,输出一个单独的行,表示经过最佳的债券购买和出售计划后,期末的资本。"}},{"title":"示例","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e1\r\n10000 4\r\n2\r\n4000 400\r\n3000 250\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e14050\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e"}}]}