题目描述

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

输入格式

共 n+1行：第 1 行：现在时间 $T_s$（几时：几分），去上学的时间 $T_e$（几时：几分），小码君院子里有几棵樱花树 n。这里的 $T_s$，$T_e$ 格式为：h:m，其中0≤h≤23，0≤m≤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% $数据：T_e-T_s \leq（即开始时间距离结束时间不超过 1000 分钟），$

$n \leq 10000。保证 T_e,T_s为同一天内的时间$。

样例解释：赏第一棵樱花树 1 次，赏第三棵樱花树 2 次。