题目描述

$\red{Farmer John }$想要带着 $\red{Bessie }$一起在科罗拉多州一起滑雪。很不幸，$\red{Bessie}$滑雪技术并不精湛。

$\red{Bessie}$了解到，在滑雪场里，每天会提供$\red{S(0<=S<=100)}$门滑雪课。第$\red{i}$节课始于$\red{M_i(1<=M_i<=10000),}$上的时间为$\red{L_i(1<=L_i<=10000)}$ 。上完第$\red{i}$节课后，$\red{Bessie}$的滑雪能力会变成$\red{A_i(1<=A_i<=100). }$注意：这个能力是绝对的，不是能力的增长值。

$\red{Bessie}$买了一张地图，地图上显示了$\red{N(1 <= N <= 10,000)}$个可供滑雪的斜坡，从第$\red{i}$个斜坡的顶端滑至底部所需的时长$\red{D_i(1<=D_i<=10000)，}$ 以及每个斜坡所需要的滑雪能力$\red{C_i(1<=C_i<=100)，}$以保证滑雪的安全性。

$\red{Bessie}$的能力必须大于等于这个等级，以使得她能够安全滑下。 $\red{Bessie}$可以用她的时间来滑雪，上课，或者美美地喝上一杯可可汁，但是她必须在$\red{T(1<=T<=10000)}$时刻离开滑雪场。这意味着她必须在$\red{T}$时刻之前完成最后一次滑雪。

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

输入格式

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

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

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

输出格式

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

样例

输入样例

10 1 2
3 2 5
4 1
1 3

输出样例

6

提示

滑第二个滑雪坡$\red{1}$次，然后上课，接着滑$\red{5}$次第一个滑雪坡