Defeat the Enemy Regionals 2014 >> Asia - Shanghai

#include<bits/stdc++.h>
using namespace std;

const int N = 1e5 + 7;

struct node1 {
    int atk, def;
    bool operator <(const node1 &x) const {
        return atk > x.atk;
    }
}a[N];

struct node2 {
    int atk, def;
    bool operator <(const node2 &x) const {
        return def > x.def;
    }
}b[N];

multiset<int> st;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    int t; cin >> t;
    int tt = t;
    while (t--) {
        st.clear();
        cout << "Case #" << tt - t << ": ";
        int n, m; cin >> n >> m;
        for (int i = 1; i <= n; i++) cin >> a[i].atk >> a[i].def;
        for (int i = 1; i <= m; i++) cin >> b[i].atk >> b[i].def;
        sort(a + 1, a + 1 + n);
        sort(b + 1, b + 1 + m);
        int ans = 0;
        int j = 1;
        for (int i = 1; i <= m; i++) {
            int atk = b[i].atk;
            int def = b[i].def;
            for (; j <= n; j++) {
                if (a[j].atk >= def) st.insert(a[j].def);
                else break;
            }
            if (!st.size()) {
                ans = -1;
                break;
            }
            multiset<int>::iterator it = st.upper_bound(atk);
            if (it == st.end()) {
                it = st.begin();
                st.erase(it);
            }
            else {
                ans++;
                st.erase(it);
            }
        }
        if (ans != -1) ans += st.size() + (n - j + 1);
        cout << ans << "\n";
    }
    return 0;
}