Gourmet Grazers

Time Limit: 3000MS Memory Limit: 65536K

Description

Like so many others, the cows have developed very haughty tastes and will no longer graze on just any grass. Instead, Farmer John must purchase gourmet organic grass at the Green Grass Grocers store for each of his N (1 ≤ N ≤ 100,000) cows.

Each cow i demands grass of price at least Ai (1 ≤ Ai ≤ 1,000,000,000) and with a greenness score at least Bi (1 ≤ Bi ≤ 1,000,000,000). The GGG store has M (1 ≤ M ≤ 100,000) different types of grass available, each with a price Ci (1 ≤ Ci ≤ 1,000,000,000) and a greenness score of Di (1 ≤ Di ≤ 1,000,000,000). Of course, no cow would sacrifice her individuality, so no two cows can have the same kind of grass.

Help Farmer John satisfy the cows’ expensive gourmet tastes while spending as little money as is necessary.

Input

  • Line 1: Two space-separated integers: N and M.
  • Lines 2…N+1: Line i+1 contains two space-separated integers: Ai and Bi
  • Lines N+2…N+M+1: Line i+N+1 contains two space-separated integers: Ci and Di

Output

  • Line 1: A single integer which is the minimum cost to satisfy all the cows. If that is not possible, output -1.

Sample Input

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

Sample Output

12

思路：

一道贪心的题目，首先要绿色分要大于奶牛，价格也要大于牛，所以先排序，可以先排绿色分，然后在个大于等于绿色分的情况下找到最低的价格，每次加起来就行了，要是找不到，就输出-1。

#include <iostream>
#include <map>
#include <algorithm>
#include <cstdio>
using namespace std;
typedef long long ll;
const int maxn = 100010;
struct NODE {
    int price;
    int green;
    bool friend operator < (NODE a, NODE b) {
        return a.green > b.green;
    }
};
NODE cow[maxn], store[maxn];
int main() {
    int n, m;
    map<int, int> mp;
    scanf("%d %d", &n, &m);
    for (int i = 0; i < n; i++) scanf("%d %d", &cow[i].price, &cow[i].green);
    sort(cow, cow + n);
    for (int i = 0; i < m; i++) scanf("%d %d", &store[i].price, &store[i].green);
    sort(store, store + m);
    int j = 0;
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        while (j < m && store[j].green >= cow[i].green) {
            mp[store[j].price]++;
            j++;
        }
        map<int, int>::iterator it = mp.lower_bound(cow[i].price);
        if (it != mp.end()) ans += it->first;
        else {
            printf("-1");
            return 0;
        }
        if (mp[it->first] == 1) mp.erase(it);
        else mp[it->first]--;
    }
    printf("%lld", ans);
    return 0;
}