程程看樱花

题目描述

程程后院里种了 $n$ 棵樱花树，每棵都有美学值 $C_i$。程程在每天上学前都会来赏花。程程可是生物学霸，他懂得如何欣赏樱花：一种樱花树看一遍过，一种樱花树最多看 $P_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$）。

输出格式

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

样例输入 #1

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

样例输出 #1

11

数据范围

• 分钟数（可用时间）不超过 $1000$
• $n \le 10000$
• $T_i, C_i$ 均为正整数
• $P_i = 0$ 表示可看无数次，$P_i > 0$ 表示最多看 $P_i$ 次
• 建议：使用 scanf() 读入时间格式

知识点与难度

本题涉及的知识点从属于 GESP 六级（混合背包 DP、时间计算），难度等级：⭐⭐⭐。

测试点分布