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
我暈的咧。。。。

周六下午的時(shí)候根本沒(méi)看著題 ，沒(méi)想到就是到水題。。。。

不過(guò)還是沒(méi)有一次AC。。。。有點(diǎn)不爽，在此膜拜xiaoz大牛，教我們?cè)S多DP

Orz。。。。

本題為經(jīng)典背包問(wèn)題O(s*n)時(shí)間度算法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        }

運(yùn)行結(jié)果:

    

        

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