
73  ZOJ Monthly, December 2008  E
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
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 Author: LI, Yaochun Source: ZOJ Monthly, December 2008 