题目描述

Farmer John 想要带着 Bessie 一起在科罗拉多州一起滑雪。很不幸，Bessie 滑雪技术并不精湛。 Bessie 了解到，在滑雪场里，每天会提供 $S(0 \le S \le 100)$ 门滑雪课。第 $i$ 节课始于 $M_i(1 \le M_i \le 10000)$ ,上的时间为 $L_i(1 \le L_i \le 10000)$ 。上完第 $i$ 节课后，Bessie 的滑雪能力会变成 $A_i(1 \le A_i \le 100)$. 注意：这个能力是绝对的，不是能力的增长值。

Bessie 买了一张地图，地图上显示了 $N(1 \le N \le 10,000)$ 个可供滑雪的斜坡，从第 $i$ 个斜坡的顶端滑至底部所需的时长$D_i(1 \le D_i \le 10000)$，以及每个斜坡所需要的滑雪能力 $C_i(1 \le C_i \le 100)$，以保证滑雪的安全性。Bessie 的能力必须大于等于这个等级，以使得她能够安全滑下。 Bessie 可以用她的时间来滑雪，上课，或者美美地喝上一杯可可汁，但是她必须在 $T(1 \le T \le 10000)$ 时刻离开滑雪场。这意味着她必须在 $T$ 时刻之前完成最后一次滑雪。

求 Bessie 在实现内最多可以完成多少次滑雪。这一天开始的时候，她的滑雪能力为 $1$ .

输入格式

第 $1$ 行：$3$ 个用空格隔开的整数：$T, S, N$ 。

第 $2 \sim S+1$ 行:第 $i+1$ 行用 $3$ 个空格隔开的整数来描述编号为 $i$ 的滑雪课：$M_i,L_i,A_i$ 。

第 $S+2 \sim S+N+1$ 行：

第 $S+i+1$行用 $2$ 个空格隔开的整数来描述第 $i$ 个滑雪坡：$C_i,D_i$ 。

输出格式

一个整数，表示 Bessie 在时间限制内最多可以完成多少次滑雪。

样例

输入样例

10 1 2
3 2 5
4 1
1 3

输出样例

6

数据范围与提示

样例解释

滑第二个滑雪坡 $1$ 次，然后上课，接着滑 $5$ 次第一个滑雪坡。

题目来源

OPEN 09 GOLD