题目描述 爱与愁大神后院里种了 n 棵樱花树，每棵都有美学值 Ci(0≤Ci≤200)。爱与愁大神在每天上学前都会来赏花。爱与愁大神可是生物学霸，他懂得如何欣赏樱花：一种樱花树看一遍过，一种樱花树最多

题目描述

爱与愁大神后院里种了 n 棵樱花树，每棵都有美学值 Ci(0≤Ci≤200)。爱与愁大神在每天上学前都会来赏花。爱与愁大神可是生物学霸，他懂得如何欣赏樱花：一种樱花树看一遍过，一种樱花树最多看Pi(0≤Pi≤100) 遍，一种樱花树可以看无数遍。但是看每棵樱花树都有一定的时间 Ti(0≤Ti≤100)。爱与愁大神离去上学的时间只剩下一小会儿了。求解看哪几棵樱花树能使美学值最高且爱与愁大神能准时（或提早）去上学。CB2100150满分答卷(100150.com)-青少年编程等级考试及竞赛题库

输入

共n+1行： 第1行：可以看樱花的时间t，爱与愁大神院子里有几棵樱花树 n。 第2行到第 n+1 行，每行三个正整数：看完第 i 棵树的耗费时间 Ti，第 i 棵树的美学值 Ci ，看第 i 棵树的次数 Pi（Pi=0 表示无数次，Pi是其他数字表示最多可看的次数 Pi）。

输出

只有一个整数，表示最大美学值。

数据范围

如果无特殊声明，则保证数据范围在整形范围以内

输入样例

10 3 2 1 0 3 3 1 4 5 4

输出样例

11