TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1924
  • 题目
  • P1924【平衡树】挑剔的美食家
    限制 : 时间限制 : 10000 MS   空间限制 : 65536 KB
    问题描述

    与很多奶牛一样,Farmer John那群养尊处优的奶牛们对食物越来越挑剔,随便拿堆草就能打发她们午饭的日子自然是一去不返了。现在,Farmer John不得不去牧草专供商那里购买大量美味多汁的牧草,来满足他那N(1 <= N <= 100,000)头挑剔的奶牛。

    所有奶牛都对FJ提出了她对牧草的要求:第i头奶牛要求她的食物每份的价钱不低于A_i(1 <= A_i <= 1,000,000,000),并且鲜嫩程度不能低于B_i(1 <= B_i <= 1,000,000,000)。

    商店里供应M(1 <= M <= 100,000)种不同的牧草,第i种牧草的定价为C_i(1 <= C_i <= 1,000,000,000),鲜嫩程度为D_i (1 <= D_i <= 1,000,000,000)。

    为了显示她们的与众不同,每头奶牛都要求她的食物是独一无二的,也就是说,没有哪两头奶牛会选择同一种食物。Farmer John想知道,为了让所有奶牛满意,他最少得在购买食物上花多少钱。

    输入格式

    第1行: 2个用空格隔开的整数:N 和 M

    第2..N+1行: 第i+1行包含2个用空格隔开的整数:A_i、B_i

    第N+2..N+M+1行: 第j+N+1行包含2个用空格隔开的整数:C_i、D_i

    输出格式

    输出1个整数,表示使所有奶牛满意的最小花费。如果无论如何都无法满足所有奶牛的需求,输出-1

    样例输入 1

    4 7
    1 1
    2 3
    1 4
    4 2
    3 2
    2 1
    4 3
    5 2
    5 4
    2 6
    4 4

    样例输出 1

    12

    样例输入 2

    10 30
    750 639
    744 277
    156 601
    93 165
    460 303
    664 433
    433 430
    163 267
    844 152
    564 603
    556 346
    423 800
    1042 1080
    924 254
    1001 983
    373 852
    1019 774
    862 113
    356 216
    1319 185
    141 177
    674 48
    939 202
    219 1415
    981 801
    157 717
    959 101
    985 453
    593 958
    579 354
    166 396
    915 477
    1214 1340
    102 847
    134 568
    753 1008
    984 665
    867 907
    1000 644
    771 887

    样例输出 2

    5804

    提示

    输出说明:
    给奶牛1吃价钱为2的2号牧草,奶牛2吃价钱为4的3号牧草,奶牛3分到价钱为2的6号牧草,奶牛4选择价钱为4的7号牧草,这种分配方案的总花费是12,为所有方案中花费最少的。


    来源  Usaco2007 Dec Gold