[USACO07DEC]美食的食草动物Gourmet Grazers

题目描述

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. 约翰的奶牛对食物越来越挑剔了。现在,商店有M 份牧草可供出售,奶 牛食量很大,每份牧草仅能供一头奶牛食用。第i 份牧草的价格为Pi,口感为 Qi。约翰一共有N 头奶牛,他要为每头奶牛订购一份牧草,第i 头奶牛要求 它的牧草价格不低于Ai,口感不低于Bi。请问,约翰应该如何为每头奶牛选 择牧草,才能让他花的钱最少?

输入输出格式

输入格式


\* 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

输出格式


\* Line 1: A single integer which is the minimum cost to satisfy all the cows. If that is not possible, output -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