Problems
철기는 지은이와 용평스키장에서 스키를 타고 싶어 한다. 그러나 아쉽게도 지은이는 스키를 그리 잘 타지 못한다.
그래서 지은이는 가까운 스키장에서 S(0 ≤ S ≤ 100) 스키 강좌를 신청했다. i번 강좌는 Mi(1 ≤ Mi ≤ 10,000)시각에 시작하여 Li(1 ≤ Li ≤ 10,000)시간동안 진행된다. i번 강좌이후에 지은이의 스키 능력은 정확히 Ai(1 ≤ Ai ≤ 100)가 된다. A_i만큼 증가하는 것이 아니라 Ai가 된다는 점에 유의하자.
지은이는 N(1 ≤ N ≤ 10,000)개의 스키 슬로프에 대한 정보가 들어있는 지도를 구입했다.그 지도에 따르면 i번 슬로프를 이용하게 되면 스키를 타고 내려올 경우 Di(1 ≤ Di ≤ 10,000)시간이 걸리고 슬로프에 올라 스키를 타고 내려오기 위해서는 Ci (1 ≤ Ci ≤ 100) 의 스키 능력치가 필요했다. 지은이의 스키능력치가 Ci 보다 크거나 같아야 i 슬로프를 이용할 수 있다.
지은이는 T(1 ≤ T ≤ 10,000)시간이 지나면 스키장을 떠나야 한다. 마지막으로 슬로프를 내려올 때는 종료시각이 넘어서는 안된다.
지은이가 제한시간을 초과하지 않고 최대 몇 번을 탈수 있는지 구하시오. 지은이의 초기 스키능력치는 1이다.
Input
첫줄에 T S N 이 입력된다.
둘째 줄부터 S+1줄에는 Mi, Li, Ai 가 입력된다.
S+2 줄부터 S+N+1줄까지는 두 개의 숫자 Ci, Di 가 입력된다.
Output
지은이가 주어진 시간 안에 스키를 탈 수 있는 최대의 회수를 출력하시오.
Example
10 1 2
3 2 5
4 1
1 3
6
지은이는 먼저 두 번째 슬로프를 한번 탄 후 레슨을 받고 첫 번째 슬로프를 5번 탄다. 따라서 모두 6번을 타게 된다.
You must sign in to write code.