Description

Ai Yu Chou has planted $n$ cherry blossom trees in the backyard, each with an aesthetic value $C_i$ ($0 < C_i \le 200$). Every morning before school, Ai Yu Chou enjoys the blossoms. As a biology ace, he knows how to appreciate them: each tree can be viewed at most $P_i$ times, where $P_i = 0$ means unlimited views; otherwise, at most $P_i$ times. Viewing tree $i$ once takes $T_i$ minutes ($0 < T_i \le 100$). Only a short time remains before he must leave for school. Determine which trees to view (and how many times) to maximize the total aesthetic value while ensuring he can leave on time (or earlier).

Input Format

There are $n+1$ lines.

Line 1: current time $T_s$ (hour:minute), school departure time $T_e$ (hour:minute), and the number of trees $n$. The formats of $T_s$, $T_e$ are hh:mm, where $0 \le hh \le 23$, $0 \le mm \le 59$, and $n$ is a positive integer.

Lines $2$ to $n+1$: three positive integers per line: the time to view tree $i$ once $T_i$, the aesthetic value of tree $i$ $C_i$, and the allowed view count $P_i$ ($P_i = 0$ means unlimited; otherwise, at most $P_i$ times).

Output Format

Output a single integer, the maximum total aesthetic value.

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

11

Hint

Constraints: For $100\%$ of the testdata, $T_e - T_s \le 1000$ (i.e., the time from start to end does not exceed $1000$ minutes), and $n \le 10000$. It is guaranteed that $T_e$ and $T_s$ are within the same day.

Sample explanation: view the first tree once, and the third tree $2$ times.

Translated by ChatGPT 5