#P1853. 投资的最大效益

投资的最大效益

题目背景

约翰先生获得了一大笔遗产,他暂时还用不上这一笔钱,他决定进行投资以获得更大的效益。银行工作人员向他提供了多种债券,每一种债券都能在固定的投资后,提供稳定的年利息。当然,每一种债券的投资额是不同的,一般来说,投资越大,收益也越大,而且,每一年还可以根据资金总额的增加,更换收益更大的债券。

题目描述

例如:有如下两种不同的债券:

  1. 投资额 $4000\$4000,年利息 $400\$400
  2. 投资额 $3000\$3000,年利息 $250\$250

初始时,有 $10000\$10000 的总资产,可以投资两份债券 1 债券,一年获得 $800\$800 的利息;而投资一份债券 1 和两份债券 2,一年可获得 $900\$900 的利息,两年后,可获得 $1800\$1800 的利息;而所有的资产达到 $11800\$11800,然后将卖掉一份债券 2,换购债券 1,年利息可达到 $1050\$1050;第三年后,总资产达到 $12850\$12850,可以购买三份债券 1,年利息可达到 $1200\$1200,第四年后,总资产可达到 $14050\$14050

现给定若干种债券、最初的总资产,帮助约翰先生计算,经过 nn 年的投资,总资产的最大值。

输入格式

第一行为三个正整数 s,n,ds, n, d,分别表示最初的总资产、年数和债券的种类。

接下来 dd 行,每行表示一种债券,两个正整数 a,ba, b 分别表示债券的投资额和年利息。

输出格式

仅一个整数,表示 nn 年后的最大总资产。

10000 4 2
4000 400
3000 250
14050

提示

对于 100%100 \% 的数据,1s1061 \le s \le {10}^62n402 \le n \le 401d101 \le d \le 101a1041 \le a \le {10}^4,且 aa10001000 的倍数,bb 不超过 aa10%10\%