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

        何老板经营的鞋店有n双鞋。每双鞋都有一定价格和尺码,对于第i双鞋,Ci表示它的价格,Si表示它的尺码。每双鞋的尺码都不相同。
        店里来了m个客户,每个客户都想买一双鞋,其中第i个客户有Di块钱,他的脚的尺码是Li。每个客户都愿意买尺码跟他脚相同或者大一码的鞋子。也就是对于j号鞋子,若满足(Cj<=Di)&&(Li==Sj||Li==Sj-1),i号客户就愿意买j号鞋。
         贪婪的何老板希望卖出去的鞋子的总价尽可能高,请你帮他算算,他最多能卖出多少钱?
         注意:一个顾客最多买一双鞋,一双鞋最多卖给一个顾客

    输入格式

    第一行,一个整数n
    接下来n行,每行两个整数Ci和Si,表示一双鞋子的价格和尺码
    接下来一行,一个整数m
    接下来m行,每行两个整数Di和Li,表示一个客户的钱和他的脚的尺码

    输出格式

    一行,一个整数,表示能卖出去的最大总额。

    样例输入 1

    3
    10 1
    30 2
    20 3
    2
    20 1
    20 2

    样例输出 1

    30

    样例输入 2

    3
    10 4
    20 5
    30 6
    2
    70 4
    50 5

    样例输出 2

    50

    提示

    对于30%的数据1<=n,m<=100

    对于100%的数据:
    1<=n<=5000
    1<=m<=10000
    1<=Ci,Si,Di,Li<=1000000000
     


    来源  改编自CF166D