题目描述

程程后院里种了 $n$ 棵樱花树，每棵都有美学值 $C_i$。程程在每天上学前都会来赏花。程程可是生物学霸，他懂得如何欣赏樱花：一种樱花树看一遍过，一种樱花树最多看 $A_i$遍，一种樱花树可以看无数遍。但是看每棵樱花树都有一定的时间 $T_i$。程程离去上学的时间只剩下一小会儿了。求解看哪几棵樱花树能使美学值最高且程程能准时（或提早）去上学。

输入格式

共 $n+1$ 行： 第 $1$行：现在时间 $T_s$（几时：几分），去上学的时间 $T_e$（几时：几分），程程院子里有几棵樱花树 $n$。这里的 $T_s$，$T_e$ 格式为：hh:mm，其中 $0\le h\le 23,0\le m\le 59$，且 $h,m,n$ 均为正整数。 第 $2$ 行到第 $n+1$ 行，每行三个正整数：看完第i棵树的耗费时间 $T_i$，第 $i$ 棵树的美学值 $C_i$，看第 $i$ 棵树的次数 $P_i$（ $P_i=0$表示无数次，$P_i$ 是其他数字表示最多可看的次数 $P_i$ ）。

输出格式

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

6:50 7:00 3
2 1 0
3 3 1
4 5 4

11

提示

$100\%$ 数据分钟数不超过 $1000$， $n\le 10000$ 建议：使用scanf()