时间限制：1秒　　内存限制：256M

---

【题目描述】

　　学校里有许多节课，第 \(i\) 节课从 \(t_i\) 时刻开始上，上课的时间为 \(s_i\)，如果上了第 \(i\) 节课，你的做题能力将变成 \(c_i\)（是能力的数值，不是能力的增长值）。

　　有 \(N\) 类作业，每类作业数量不限，每类作业完成一份所需要的时间为 \(a_i\)，做某类作业需要的做题能力达到 \(q_i（≥q_i）\)才能完成。

　　在每个时刻你可以选择上课、休息、做作业，如果选择上课则必须上完整节课，如果选择做作业必须花完整的 \(a_i\) 时间做，同一时刻只能上一节课或做一份作业。而且人的精力有限，在 \(T+1\) 时刻后必须停止学习（部分课可能上到 \(T+1\) 时刻后）。求在时限内最多可以完成几份作业。在刚开始时，你的做题能力为 1，时刻为 1。

【输入格式】

　　第一行三个整数 \(T，M，N\)，表示总时间为 \(T\)，有 \(M\) 节课，有 \(N\) 类作业。
　　接下来 \(M\) 行每行三个整数 \(t_i，s_i，c_i\)。
　　接下来 \(N\) 行每行两个整数 \(a_i，q_i\)。

【输出格式】

　　共一行，一个整数，表示时限内最多可以完成几份作业。

【输入输出样例1】

　Input

10 1 2
3 2 5
4 1
1 3

　Output

6

【输入输出样例2】

　Input

15 4 4
6 1 5
11 2 1
5 4 5
4 5 3
4 1
1 3
2 3
1 1

　Output

15

【数据限制】

　　对于 \(20\%\) 的数据，\(1≤M,N≤4\)，\(1≤T≤15\)
　　对于 \(50\%\) 的数据，\(1≤M≤100\)，\(1≤N≤1000\)，\(1≤T≤1000\)
　　对于 \(20\%\) 的数据，\(1≤M≤1000\)，\(1≤N≤100000\)，\(1≤T≤100000\)，\(1≤c_i,q_i≤100\)，\(t_i≤T\)

【来源】

　　Mr.he