【cogs754】[USACO Open09]滑雪训练

2014年3月31日1,7000

农夫约翰想带着他的奶牛Bessie去佛罗里达滑雪,可是,Bessie的滑雪技术真是太差了。

她了解到滑雪学校全天提供滑雪课程,共有S(0 <= S <=100)个滑雪课程可供选择,课程i从时间M_i(1 <= M_i <= 10,000)开始,持续时间为L_i(1 <= L_i <= 10,000),学完该课程滑雪水平将提升至A_i(1 <= A_i <= 100),注意:滑雪水平的提升是绝对的,而不是累加的。

此外Bessie还买了一张滑雪练习场的地图,从图中可以看到练习场每个斜坡的详细情况:从坡上滑下来所需的时间D_i(1 <= D_i <= 10,000),以及滑这个坡所需要的水平等级C_i(1 <= C_i <= 100),为安全起见,只有滑雪水平高于该坡所要求的等级,才可以从这个坡滑下。

Bessie可以把她所有的时间都花在滑雪、上课上,当然她也可以去喝杯热可可,但前提是她必须得在滑雪学校待至时间T(1 <= T <= 10,000),这也意味着她的最后一趟滑坡行动不得超过这个时限。

请确定在这个时间段内,Bessie最多可以滑多少趟斜坡,假定她当天的起始水平为1。

输入格式:
第1行,三个空格隔开的整数:T,S,N;
第2~S+1行,第i+1行有三个空格隔开的整数M_i,L_i,A_i,描述了一个课程的情况;
第S+2~S+N+1行,第S+i+1行为两个空格隔开的整数,C_i,D_i,描述了一个斜坡的情况。

输出格式:
一行,一个整数,即在时限内Bessie能完成的滑坡的最大次数。

样例:
ski.in
10 1 2
3 2 5
4 1
1 3

ski.out
6

输出数据说明
先滑一次第2个斜坡,然后在时间3去上课,上课至时间5,然后在时间结束之前可以再滑五次第1个斜坡,所以共6次滑坡。

题解