题目描述

辰辰是个天资聪颖的孩子，他的梦想是成为世界上最伟大的医师。为此，他想拜附近最有威望的医师为师。医师为了判断他的资质，给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说：“孩子，这个山洞里有 $n$ 种草药，每种草药都有一个价值 $C_i(0 \le C_i \le 200)$ ，有些草药再生能力极强，可以无限制地多次采摘，另一些草药则数量有限，最多采 $P_i(0 \le P_i \le 100)$ 次。采摘一种草药需要耗时 $T_i$ 。如果你是一个聪明的孩子，你应该能在规定的时间内让采到的草药的总价值最大。”

如果你是辰辰，你能完成这个任务吗？

输入格式

共 $n+1$行：

第 $1$ 行：开始采药的时间 $T_b$（几时：几分），结束采药的时间 $T_e$（几时：几分），山洞里有 $n$ 种草药。这里的 $T_b$，$T_e$ 格式为：小时:分钟（为24小时记法）

第 $2$ 行到第 $n+1$ 行，每行三个正整数：采 $i$ 种草药的耗费时间 $T_i$，第 $i$ 种草药的价值 $C_i$，第 $i$ 种草药可供采摘的次数 $P_i$（$P_i=0$ 表示无数次，$P_i$ 是其他数字表示最多可以采摘的次数 $P_i$）。

输出格式

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

6:47 7:01 3
2 1 0
3 3 1
4 5 4

16

提示

$100\%$ 数据：开始采药的时间距离采药结束的时间至多为 $1000$ 分钟，$n \leq 10000$。并且保证 $T_e,T_b$ 为同一天内的时间。

样例解释：采第一种草药一次，采第三种草药 $3$ 次。