J17 习题-7 樱花

题目描述

佩奇在后院里种了$n$ 棵樱花树，每棵都有美学值 $c_i$。佩奇在每天上学前都会来赏花。有的樱花树最多看一遍就过，有的樱花树最多看 $a_i$遍，有的樱花树则可以看无数遍。但是看每棵樱花树都有一定的时间$t_i$ 。而佩奇离去上学的时间只剩下$T$个单位时间了。求看哪几棵樱花树能使美学值最高且佩奇能准时（或提早）去上学。

输入格式

共 $n+1$行：

第 $1$行：上学剩余的时间$T$，院子里有樱花树的数量$n$。

第 $2$ 行到第 $n+1$行，每行三个正整数：看完第 $i$棵树的耗费时间 $t_i$，第 $i$ 棵树的美学值 $c_i$，看第 $i$ 棵树的最多次数 $p_i$（$p_i=0$表示无数次，$P_i$是其他数字表示最多可看的次数$p_i$）

输出格式

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

样例输入

10 3
2 1 0
3 3 1
4 5 4

样例输出

11

数据范围

对于 $50\%$ 数据：$T\leq 100$，$n \leq 1000$。

对于 $100\%$ 数据：$T\leq 1000$，$n \leq 10000$。