[USACO07DEC] Gourmet Grazers G

题目描述

约翰的奶牛对食物越来越挑剔了。现在，商店有 $m$ 份牧草可供出售，奶牛食量很大，每份牧草仅能供一头奶牛食用。第 $i$ 份牧草的价格为 $p_i$，口感为 $q_i$。

约翰一共有 $n$ 头奶牛，他要为每头奶牛订购一份牧草，第 $i$ 头奶牛要求 它的牧草价格不低于 $a_i$，口感不低于 $b_i$。请问，约翰应该如何为每头奶牛选择牧草，才能让他花的钱最少？

输入格式

第一行，两个整数 $n$ 和 $m$。

第 $2\sim n+1$ 行，第 $i+1$ 行两个整数 $a_i$ 和 $b_i$。

第 $n+2\sim n+m+1$ 行，第 $i+n+1$ 行两个整数 $c_i$ 和 $d_i$。

含义见题面所述。

输出格式

输出仅一行，代表能够满足所有奶牛要求所要花的钱的最小值。如果不能够满足所有奶牛的要求，输出 -1。

数据范围

对于 $100\%$ 的数据，满足 $1\leqslant n\leqslant 10^5$，$1\leqslant a_i,b_i,c_i,d_i\leqslant 10^9$。

样例输入 #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 元;
第二头牛吃第三份草，花 4 元;
第三头牛吃第六份草，花 2 元;
第四头牛吃第七份草，花 4 元