TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P4266
  • 题目
  • P4266上课
    限制 : 时间限制 : - MS   空间限制 : 265536 KB
    评测说明 : 1s
    问题描述

    学校里有许多节课,第 i 节课从 ti 时刻开始上,上课的时间为 si,如果上了第 i 节课,你的做题能力将变成 ci(是能力的数值,不是能力的增长值)。有 N 类作业,每类作业数量不限,每类作业完成一份所需要的时间为 ai,做某类作业需要的做题能力达到 qi(>=qi)

     

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

    输入格式

    第一行三个整数 T,M,N,表示总时间,有 M 节课,有 N 类作业。

     

    接下来 M 行每行三个整数 ti,si,ci。

     

    接下来 N 行每行两个整数 ai,qi。

    输出格式

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

    样例输入

    10 1 2

    3 2 5

    4 1

    13

    样例输出

    6

    提示

    【数据规模】

     

    20%的数据满足 M,N<=4,T<=15。

     

    50%的数据满足 M<=100,N<=1000,T<=1000。

     

    100%的数据满足 M<=1000, N<=100000, T<=100000, 1<=ci<=100, 1<=ai、 ti<=T,1<=qi<=100。