TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  信息发布  解题排行
  • 首页
  • 题库
  • P3827
  • 题目
  • P3827火车运输
    限制 : 时间限制 : - MS   空间限制 : 265536 KB
    评测说明 : 1000ms
    问题描述

    ByteLand火车站(编号0)每天都要发往全国各地N列客运火车,编号1 N。第i列火车的目的地是编号Si的火 车站。 对任意车站X,都与X+1车站有铁轨直接相连,因此火车站可以看成数轴上的整数点,第i列火车可以停靠区 间[0, Si]中的各个站点。每列火车装载乘客的最大容量为Ci。 有M个人需要乘坐火车。已知每个人的乘车区间为[Li, Ri],即是说,在Li上车,在Ri下车。 由于火车的容量限制,请你求出最多有多少人的乘车需求可以得到满足。
     

    输入格式

    第1行:2个整数N和M。
    接下来N行,每行2个整数Si和Ci,表示第i辆车的目的站和容量。
    接下来M行,每行2个整数Li和Ri,表示第i个乘客的乘车区间。
     

    输出格式

    第1行:1个整数,表示最多有多少乘客的乘车需求可以满足
     

    样例输入

    1 3 
    10 2 
    1 5 
    3 7 
    4 9

    样例输出

    2

    提示

    1 ≤ N,M ≤ 10^5
    1 ≤ Si,Ci ≤ 10^9
    1 ≤ Li ≤ Ri ≤ 10^9
     


    来源  八中