#528. 希蒙的赏樱计划

希蒙的赏樱计划

题目描述

希蒙后院里种了 n 棵樱花树,每棵都有美学值 CiC_i 。希蒙在每天上学前都会来赏花。希蒙可是生物学霸,他懂得如何欣赏樱花:一种樱花树看一遍过,一种樱花树最多看 AiA_i遍,一种樱花树可以看无数遍。但是看每棵樱花树都有一定的时间 TiT_i。希蒙离去上学的时间只剩下一小会儿了。求解看哪几棵樱花树能使美学值最高且希蒙能准时(或提早)去上学。

输入格式

共 n+1行:第 1 行:现在时间 TsT_s(几时:几分),去上学的时间 TeT_e(几时:几分),希蒙院子里有几棵樱花树 n。这里的 TsT_sTeT_e 格式为:h:m,其中0≤h≤23,0≤m≤59,且 h,m,n均为正整数。

第 2 行到第 n+1 行,每行三个正整数:看完第 i 棵树的耗费时间 TiT_i,第 i 棵树的美学值 CiC_i,看第 i 棵树的次数 PiP_iPiP_i=0表示无数次,P_i是其他数字表示最多可看的次数 PiP_i )。

输出格式

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

样例

输入样例

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

输出样例

11

数据范围与提示

100% 数据:TeTs(即开始时间距离结束时间不超过1000分钟),数据:T_e-T_s \leq(即开始时间距离结束时间不超过 1000 分钟),

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

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