I 充分利用学习卡(粉)
Time Limit:1000MS Memory Limit:65536K
Total Submit:3 Accepted:0
Description
现在王同学一张树人学习卡，他想报一些课程，每节课程都有一定的花费p、知识量v，每周每种课程上n节。他现在想用这张卡在这周内获得最多的知识量。请各位帮王同学用编程解决这个问题。
Input
第一行输入两个数据cash(卡的价值0<=cash<=1000) N(课程的种类数0<=N<=10),
第2行输入每种课程的信息，包括p(花费0<=p<=1000),v(知识量0<=v<=1000),n(每周课程节数0<=n<=20)，格式为:
p1 v1 n1 p2 v2 n2 p3 v3 n3...pN vN nN
(cash = -1 && N == -1时结束输入)
Output
输出获得的最大知识量。
Sample Input
735 3 125 125 4 5 5 6 350 350 3 0 3 1 2 1 2 2 1 3 3 1 10 1 1 5 1 -1 -1
Sample Output
735 0 5