Ski Lessons

Farmer John wants to take Bessie skiing in Colorado. Sadly, Bessie is not a very good skier.

The ski resort offers $S$ ski lessons throughout the day ($0 \le S \le 100$). Lesson $i$ starts at time $M_i$ and lasts for $L_i$ units of time ($1 \le M_i \le 10000$, $1 \le L_i \le 10000$). When lesson $i$ finishes (i.e. at time $M_i + L_i$), Bessie's skill level becomes $A_i$ ($1 \le A_i \le 100$). This is an absolute value that overwrites her skill, not an increment.

The resort has $N$ ski slopes ($1 \le N \le 10000$). Skiing down slope $i$ once takes $D_i$ units of time ($1 \le D_i \le 10000$) and requires a skill level of at least $C_i$ to descend safely ($1 \le C_i \le 100$). Bessie may descend slope $i$ only when her skill level is at least $C_i$. She may ski any slope as many times as she likes, and each descent counts as one run.

Bessie can spend her time skiing, taking lessons, or resting (sipping hot cocoa), but she can only do one thing at a time. A lesson starts at its fixed time $M_i$, so to attend it she must be free (not in the middle of a descent or another lesson) at exactly time $M_i$.

Bessie starts the day at time $0$ with skill level $1$ and must leave the resort by time $T$ ($1 \le T \le 10000$); that is, she must complete the descent of her last slope without exceeding time $T$.

Find the maximum number of runs Bessie can complete within the time limit.

• Line 1: three space-separated integers $T$, $S$, and $N$
• Next $S$ lines: line $i$ describes lesson $i$ with three space-separated integers $M_i$, $L_i$, and $A_i$
• Next $N$ lines: line $i$ describes slope $i$ with two space-separated integers $C_i$ and $D_i$

Print a single integer on its own line: the maximum number of runs Bessie can complete within the time limit.

One optimal strategy is: ski the slope with $C = 1$, $D = 3$ once (time $0 \to 3$), take the lesson that starts at time $3$ to raise the skill level to $5$ (time $3 \to 5$), then ski the slope with $C = 4$, $D = 1$ five times before time runs out (time $5 \to 10$), for a total of $6$ runs.