6114번 - Ski Lessons 다국어

문제

Farmer John wants to take Bessie skiing in Colorado. Sadly, Bessie is not really a very good skier.

Bessie has learned that the ski resort is offering S (0 <= S <= 100) ski classes throughout the day. Lesson i starts at time M_i (1 <= M_i <= 10,000) and lasts for time L_i (1 <= L_i <= 10,000). After lesson i, Bessie's ski ability becomes A_i (1 <= A_i <= 100). Note: this ability is an absolute, not an incremental change.

Bessie has purchased a map which shows all N (1 <= N <= 10,000) ski slopes along with the time D_i (1 <= D_i <= 10,000) required to ski down slope i and the skill level C_i (1 <= C_i <= 100) required to get down the slope safely. Bessie's skill level must be greater than or equal to the skill level of the slope in order for her to ski down it.

Bessie can devote her time to skiing, taking lessons, or sipping hot cocoa but must leave the ski resort by time T (1 <= T <= 10,000), and that means she must complete the descent of her last slope without exceeding that time limit.

Find the maximum number of runs Bessie can complete within the time limit. She starts the day at skill level 1.

입력

• Line 1: Three space-separated integers: T, S, and N
• Lines 2..S+1: Line i+1 describes ski lesson i with three space-separated integers: M_i, L_i, and A_i
• Lines S+2..S+N+1: Line S+i+1 describes ski slope i with two space-separated integers: C_i and D_i.

출력

A single integer on a line by itself, the maximum number of runs that Bessie may ski within the time limit.

제한

힌트

Ski the second slope once, take the lesson, and ski the first slope 5 times before time is up: a total of 6 slopes.