Ski Lessons

Time limit1sMemory limit128 MB

Summary

Given ski lessons that overwrite Bessie's skill at fixed start times and slopes with skill and time costs, maximize the number of runs by time T.

Level: Medium7 of 10
Topics: Dynamic programming, Greedy, Sorting, Binary search
Solved: No attempts yet

Problem

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.

Input

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$

Output

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

Hint

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.

Examples3

Example 1
Input
```
10 1 2
3 2 5
4 1
1 3
```
Expected output
```
6
```
Example 2
Input
```
10 0 1
1 2
```
Expected output
```
5
```
Example 3
Input
```
5 0 1
2 1
```
Expected output
```
0
```