스키 강습

Farmer John은 Bessie를 콜로라도로 스키 여행에 데려가려 합니다. 하지만 Bessie는 스키 실력이 그리 좋지 않습니다.

스키 리조트에서는 하루 동안 $S$개의 스키 강습을 제공합니다 ($0 \le S \le 100$). $i$번째 강습은 시각 $M_i$에 시작하여 $L_i$ 시간 동안 진행됩니다 ($1 \le M_i \le 10000$, $1 \le L_i \le 10000$). 강습이 끝나면(즉 시각 $M_i + L_i$에) Bessie의 스키 실력은 $A_i$가 됩니다 ($1 \le A_i \le 100$). 이 값은 증가량이 아니라 실력을 그 값으로 덮어쓰는 절대적인 값입니다.

리조트에는 $N$개의 슬로프가 있습니다 ($1 \le N \le 10000$). $i$번째 슬로프를 한 번 내려오는 데는 $D_i$ 시간이 걸리며 ($1 \le D_i \le 10000$), 안전하게 내려오려면 실력이 $C_i$ 이상이어야 합니다 ($1 \le C_i \le 100$). 즉 Bessie의 실력이 슬로프가 요구하는 실력 이상일 때에만 그 슬로프를 내려올 수 있습니다. 같은 슬로프를 원하는 만큼 여러 번 내려올 수 있으며, 하강 한 번이 한 번의 완주로 계산됩니다.

Bessie는 스키를 타거나, 강습을 듣거나, 쉬면서(코코아를 마시며) 시간을 보낼 수 있지만 한 번에 한 가지만 할 수 있습니다. 강습은 정해진 시각 $M_i$에 시작하므로, 그 강습을 들으려면 시각 $M_i$에 다른 일(슬로프 하강 등)을 하고 있지 않고 자유로운 상태여야 합니다.

Bessie는 시각 $0$에 실력 $1$로 하루를 시작하며, 시각 $T$까지는 리조트를 떠나야 합니다 ($1 \le T \le 10000$). 즉 마지막 슬로프를 내려오는 것까지 시각 $T$를 넘기지 않고 끝내야 합니다.

시간 제한 안에 Bessie가 완주할 수 있는 슬로프 하강의 최대 횟수를 구하세요.

• 첫째 줄: 공백으로 구분된 세 정수 $T$, $S$, $N$
• 다음 $S$개 줄: 각 줄에 $i$번째 강습을 나타내는 세 정수 $M_i$, $L_i$, $A_i$
• 다음 $N$개 줄: 각 줄에 $i$번째 슬로프를 나타내는 두 정수 $C_i$, $D_i$

시간 제한 안에 Bessie가 완주할 수 있는 슬로프 하강의 최대 횟수를 한 줄에 정수 하나로 출력합니다.

최적 전략의 하나는 다음과 같습니다. 먼저 실력 $1$로도 탈 수 있는 슬로프($C = 1$, $D = 3$)를 한 번 내려오고(시각 $0 \to 3$), 시각 $3$에 시작하는 강습을 들어 실력을 $5$로 올린 뒤(시각 $3 \to 5$), 시간이 다 될 때까지 슬로프($C = 4$, $D = 1$)를 다섯 번 내려옵니다(시각 $5 \to 10$). 모두 합쳐 $6$번을 완주합니다.