当前没有测试数据。

题目描述

小明是一位热爱阅读的学生。学校附近的书店正在进行促销活动，小明想趁此机会购买一些书籍。

小明有 M 元零花钱，书店有 n 种书籍在售。每种书籍都有其售价、对小明的价值评分，以及书店的库存数量。由于书店促销，每种书籍每人限购不超过其库存数量。

小明希望用他的零花钱购买书籍，使得所有购买的书籍的总价值评分最大化。注意，每种书最多只能购买库存数量本。

输入格式

第一行两个整数 M 和 n，分别表示小明的零花钱总额和书籍种类数。

接下来 n 行，每行三个整数 price、value、stock，分别表示该书籍的单价、价值评分、库存数量。

输出格式

一个整数，表示能获得的最大价值评分。

样例输入

100 4
20 60 3
15 40 5
30 80 2
25 55 4

样例输出

295

样例解释

最优购买方案：

• 第1种书买2本：花费40元，价值120
• 第2种书买0本
• 第3种书买2本：花费60元，价值160
• 第4种书买0本

总花费100元，总价值280元。

或者另一种方案：

• 第1种书买3本：花费60元，价值180
• 第3种书买1本：花费30元，价值80
• 第4种书买0本 总花费90元，价值260元，不如上面的方案。

再试一种：

• 第1种书买3本：花费60元，价值180
• 第3种书买1本：花费30元，价值80 剩余10元无法再购买。

实际上最优方案：

• 第1种书买2本：40元，价值120
• 第3种书买2本：60元，价值160 总花费100元，价值280元。

但还可以买第2种书：

• 第1种书买1本：20元，价值60
• 第3种书买2本：60元，价值160
• 第2种书买1本：15元，价值40 但花费95元，价值260元。

最优解应该是：第1种买3本（60元，180价值）+ 第3种买1本（30元，80价值）= 90元，260价值，剩余10元可以买第2种书不够。不对，还剩10元可以买不了第2种书（15元）。

让我重新计算：

• 第1种买3本：60元，180价值，剩余40元
• 第3种买1本：30元，80价值，剩余10元
• 无法继续购买 总价值260

或者：

• 第3种买2本：60元，160价值，剩余40元
• 第1种买2本：40元，120价值，剩余0元 总价值280

这就是最优解！

数据范围

对于 30% 的数据：M ≤ 100, n ≤ 20 对于 60% 的数据：M ≤ 5000, n ≤ 100 对于 100% 的数据：M ≤ 10000, n ≤ 500，每种书籍价格和价值均不超过 1000，库存不超过 100