题意描述

与很多奶牛一样，Farmer John那群养尊处优的奶牛们对食物越来越挑剔，随便拿堆草就能打发她们午饭的日子自然是一去不返了。

现在，Farmer John不得不去牧草专供商那里购买大量美味多汁的牧草，来满足他那$n$头挑剔的奶牛。

所有奶牛都对Farmer John提出了她对牧草的要求：第$i$头奶牛要求她的食物每份的价钱不低于$a_i$，并且鲜嫩程度不能低于$B_i$。

商店里供应有$m$种不同的牧草，第$i$种牧草的定价为$c_i$，鲜嫩程度为$d_i$。

并且，奶牛们为了显示她们的与众不同，每头奶牛都要求她的食物是独一无二的，也就是说，没有哪两头奶牛会选择同一种食物。

Farmer John想知道，为了让所有奶牛满意，他最少得在购买食物上花多少钱？

输入格式

第一行包含两个整数$n,m$，分别表示奶牛的数量与牧草数量。

第$2$行到第$n + 1$行每行包含$2$个用空格隔开的整数，分别为$a_i$与$b_i$。

第$n+2$行到第$n+m+1$行，每行包含$2$个用空格隔开的整数，分别为$c_i$与$d_i$。

输出格式

输出仅有一行，包含一个整数，即最小花费。

若无法满足要求，则输出-1即可。

Input & Output ‘s examples

Input ‘s eg

Output ‘s eg

样例解释

给奶牛$1$吃价钱为$2$的$2$号牧草，奶牛$2$吃价钱为$4$的$3$号牧草，奶牛$3$分到价钱为$2$的$6$号牧草，奶牛$4$选择价钱为$4$的$7$号牧草，这种分配方案的总花费是$12$。

可以证明，这是所有方案中花费最少的。

数据范围与约定

对于$30\%$的数据，保证$1 \leq n,m \leq 1000$，

对于$100\%$的数据，保证$1 \leq n , m \leq 10^5$，$1 \leq a_i , b_i , c_i , d_i \leq 10^9$

分析

比较明显的一道贪心。

贪心的思路也比较简单，只要先满足美味度要求较高的奶牛，对于美味度要求相同的话，则先满足价格要求低的。

证明也很容易，不难看出，对于第$i$头奶牛，它可以吃的牧草第$i + 1$头奶牛也一定能吃，因为我们先满足了美味度要求较高的奶牛。

则我们在枚举每一头奶牛时记录一下现在记录到了哪一个牧草，然后只记录后面的牧草，把该奶牛能吃的牧草加入待选牧草中。选择时选择待选牧草中不低于当前奶牛价格要求的牧草中价值最小的牧草即可。

但是，上述做法直接实现的复杂度是$O(n^2)$的，而且很不好写。需要使用数据结构优化。

重新梳理一下上面的思路，发现我们需要写一种支持以下$3$种操作的数据结构，分别是

插入一个元素
删除一个元素
查询不小于某元素的第一个数，即该元素的后继。

Fhq_Treap即可。

剩下的见代码注释。

Code[Accepted]

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
#include<stack>
#include<queue>
#include<deque>
#include<vector>
#include<algorithm>
#include<iomanip>
#include<cstdlib>
#include<cctype>
#include<cmath>

#define ll long long
#define I inline
#define N 100001

using namespace std;

namespace Treap{
    #define lson(x) node[x].l
    #define rson(x) node[x].r

    ll node_num , root;

    struct Node{
        ll dis;
        ll size;
        ll rd;
        ll l , r;
        Node(ll dis = 0) : dis(dis) , size(1) , rd(rand()) , l(0) , r(0) {};
    }node[N];

    I void update(ll x){  
        node[x].size = (lson(x) ? node[lson(x)].size : 0) + (rson(x) ? node[rson(x)].size : 0) + 1; 
    }

    void spilt(ll n , ll k , ll &x , ll &y){  
        if(!n) x = y = 0;
        else if(node[n].dis > k){
            spilt(lson(n) , k , x , y);
            lson(n) = y;
            update(y = n);
        }
        else{
            spilt(rson(n) , k , x , y);
            rson(n) = x;
            update(x = n);
        }
    }

    ll merge(ll x , ll y){ 
        if(!x || !y) return x + y;
        if(node[x].rd < node[y].rd){
            rson(x) = merge(rson(x) , y);
            update(x);
            return x;
        }
        else{
            lson(y) = merge(x , lson(y));
            update(y);
            return y;
        }
    }

    void insert(ll k){
        ll x , y;
        spilt(root , k , x , y);
        node[++ node_num] = Node(k);
        root = merge(merge(x , node_num) , y);
    }

    void remove(ll k){
        ll x , y , z;
        spilt(root , k , x , z);
        spilt(x , k - 1 , x , y);
        y = merge(lson(y) , rson(y));
        root = merge(merge(x , y) , z);
    }

    I ll upper(ll k){
        ll x , y , t;
        spilt(root , k - 1, x , y);
        t = y;
        while(lson(t)){
            t = lson(t);
        }
        root = merge(x , y);
        return node[t].dis;
    }

}

ll n , m;

struct Cow{
    ll val , del;
}cow[N];

bool cmp1(Cow a , Cow b){
    return a.del > b.del;
}

struct Cao{
    ll val , del;
}cao[N];

bool cmp2(Cao a , Cao b){
    return a.del > b.del;
}

int main(){
    cin >> n >> m;
    for(int i = 1; i <= n; i ++){
        cin >> cow[i].val >> cow[i].del;
    }
    for(int i = 1; i <= m; i ++){
        cin >> cao[i].val >> cao[i].del;
    }
    sort(cow + 1 , cow + 1 + n , cmp1); //先将奶牛与牧草分别按照美味度降序排序。
    sort(cao + 1 , cao + 1 + m , cmp2);
    ll tmp , num = 1 , ans = 0;
    for(int i = 1; i <= n;  i ++){
        tmp = -1;
        while(cao[num].del >= cow[i].del && num <= m){  
            Treap :: insert(cao[num].val);  //将这头奶牛能吃的牧草全部加入待选牧草
            num ++;
        }
        tmp = Treap :: upper(cow[i].val);   //寻找该奶牛要求的后继
        if(tmp == -1){  //若找不到，则证明无解
            cout << "-1" << "\n";
            return 0;
        }
        ans += tmp; //记录答案
        Treap :: remove(tmp);   //删除该牧草
    }
    cout << ans << "\n";
    return 0;
}