1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55---
layout: post
title: "每周ACM之二：小小的大背包"
date: 2013-12-31 12:00:00
category: acm
summary: "每周ACM，第二期，小小的大背包。"
from: http://acm.hdu.edu.cn/showproblem.php?pid=2191
---
山岭巨人 —— 小小，作为近卫一方，身体最庞大的英雄（当然是长大之后）。
为此，冰蛙大大，为小小赋予了一项新的特性 —— 背包无限，也就是说只要小小有钱，他可以买无限个装备，我想以他的身躯，足够装下。
现在，假设山岭巨人身上有N个金币。
现在有M种装备，每种装备都有售价P，一定的价值H，和库存量C。
请计算出，小小怎么买装备才能使总价值最高？
### Input
输入数据首先包含一个正整数C，
表示有C组测试用例；
每组测试用例的第一行是两个整数N和M(1<=N<=10000, 1<=m<=100)，
分别表示小小拥有的金币数和装备的种类数；
然后是M行数据，每行包含3个数P，H和C(1<=P<=2000, 1<=H<=200, 1<=C<=20)，
分别表示装备的价格、装备的价值以及对应装备的库存量。
（备注：N、P都是以100为基数）。
### Output
对于每组测试数据，请输出能够购买装备的最大价值。
### Sample Input
{% highlight text %}
1
800 2
200 100 4
400 100 2
{% endhighlight %}
### Sample Output
{% highlight text %}
400
{% endhighlight %}
**答案敬请期待**