题目描述

小丽在植物园里发现了 $n$ 棵不同品种的花，每种花有一个观赏价值 $C_i$（$0 \lt C_i \le 200$）。小丽想在有限的时间内尽可能多地欣赏花卉。

每种花有不同的观赏规则：

• 有的花只能看一遍（$P_i = 1$）
• 有的花最多看 $P_i$ 遍（$0 \lt P_i \le 100$）
• 有的花可以看无数遍（$P_i = 0$）

每看一遍第 $i$ 棵花需要花费 $T_i$（$0 \lt T_i \le 100$）分钟。小丽从 $T_s$ 开始赏花，必须在 $T_e$ 之前（含 $T_e$）出发去上课。

求小丽能获得的最大观赏价值总和。

输入格式

共 $n + 1$ 行：

第 $1$ 行：当前时间 $T_s$（格式 hh:mm），出发时间 $T_e$（格式 hh:mm），花的品种数 $n$。其中 $0 \le hh \le 23$，$0 \le mm \le 59$，$hh$、$mm$、$n$ 均为非负整数。

第 $2$ 行到第 $n + 1$ 行：每行三个非负整数 $T_i$、$C_i$、$P_i$，分别表示第 $i$ 种花每遍观赏耗时、观赏价值、最多观赏次数（$P_i = 0$ 表示无限次）。

输出格式

一个整数，表示最大观赏价值。

样例

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

11

提示

$100\%$ 数据：$T_e - T_s \le 1000$（即可用时间不超过 $1000$ 分钟），$n \le 10000$。保证 $T_s$ 和 $T_e$ 在同一天内。

样例解释：赏第 $1$ 种花一次（价值 $1$），赏第 $3$ 种花两次（价值 $5 \times 2 = 10$），共 $11$。