베시는 그 스키장에서 S (0 ≤ S ≤ 100)번의 스키 수업을 하루 동안 받았다. 수업 i는 M_i (1 ≤ M ≤ 10,000)에 시작하여 L_i (1 ≤ L_i ≤ 10,000)동안 진행된다. 수업 i를 받은 후, 베시의 스키 실력은 A_i(1 ≤ A_i ≤ 100)만큼 향상된다. 참고로 이 능력은 시간이 지나도 변하지 않는다.

베시는 N(1 ≤ N ≤ 10,000)개의 슬로프와 낙하 시간 D_i (1 ≤ D_i ≤ 10,000), 안전을 위해 요구되는 스키 실력 C_i(1 ≤ C_i ≤ 100)가 나와 있는 지도를 샀다. 베시가 스키를 타려면 스키 실력이 이보다 좋거나 같아야 한다.

베시는 그녀의 시간을 스키를 타고, 수업을 받고, 뜨거운 코코아를 마시는 데 시간을 낼 수 있으나 반드시 스키장을 T(1 ≤ T ≤ 10,000)시간 안에 떠나야 하며, 이는 그녀가 그 시간을 초과하지 않고 마지막 슬로프 하강을 마쳐야 한다는 것이다.

베시가 제한시간 내에 몇 번이나 스키를 탈 수 있는지를 구하라. 그녀는 스키 실력 1부터 시작한다.

입력

• 첫 줄에는 T와 S, N이 순서대로 입력된다.
• 둘째 줄부터 S+1번째 줄에는 M_i, L_i, A_i가 순서대로 입력된다.
• S+2번째 줄부터 S+N+1 줄에는 C_i와 D_i가 입력된다.

출력

입출력 예

입력 

10 1 2 
3 2 5 
4 1 
1 3 

출력 

6 

출력 보충

출처:usaco 2009 gold
번역:abc