watashi's mm is so pretty as well as clever. When she has to move to YQ from ZJG, she turns to watashi for help to move her baggages to the baggage office from her dormitory.

Now watashi has initially total strength s. Because there are so many baggages, watashi may be unable to move all baggages to the baggage office. So, watashi decides to make a perfect plan to reduce the loss.

Every baggage has three property values v, a, b, that is

• v: the value of this baggage
• a: if watashi wants to move this baggage, the must have no less than a strength left. And if he moves this baggage to baggage office, he will loss a strength.
• b: after watashi moves this baggage and walks back to dormitory, he can recover b strength.

Now watashi is thinking how can he reduce the least loss, that is to make the total value of baggages in the baggage office largest. Can you help him?

Input

There are multiple cases, the first line contains an integer T, representing the number of test cases.

The first line of each case is two integers, s and n. 10 <= s <= 1000 is the initial strength. 1 <= n <= 100 is the number of baggages.

The next n lines represents the baggages, each line has three integers 0 <= v, a, b <= 1000 and a > b.

Output

An integer V for each case representing the total value baggage that watashi can move to baggage office.

Sample Input

1
9 3
12 3 1
13 3 1
14 7 2

Sample Output

27
我晕的咧。。。。

周六下午的时候根本没看着题 ，没想到就是到水题。。。。

不过还是没有一次AC。。。。有点不爽，在此膜拜xiaoz大牛，教我们许多DP

Orz。。。。

本题为经典背包问题O(s*n)时间度算法O（s）空间度。

核心程序如下
 1for(i=0;i<n;i++)
 2        {
 3            for(j=st;j>=0;j--)
 4                if(maxb[j]!=MAX&&j+b[i].a<=st)
 5                {
 6                    int t=j+b[i].a-b[i].b;
 7                    if(maxb[t]!=MAX)maxb[t]=maxb[t]>maxb[j]+b[i].v?maxb[t]:maxb[j]+b[i].v;
 8                    else maxb[t]=maxb[j]+b[i].v;
 9                    if(sum<maxb[t])sum=maxb[t];
10                }    
11        }

运行结果:

    

        

            
2008-12-28 23:51:11
            
C++
            
0
            
180
            
聖*騎士