#P5654. 挑剔的美食家

挑剔的美食家

题目描述

与很多奶牛一样,FarmerJohn{Farmer John}那群养尊处优的奶牛们对食物越来越挑剔,随便拿堆草就能打发她们午饭的日子自然是一去不返了。现在,FarmerJohn{Farmer John}不得不去 牧草专供商那里购买大量美味多汁的牧草,来满足他那N(1<=N<=100,000){N(1 <= N <= 100,000)}头挑剔的奶牛。

所有奶牛都对FJ{FJ}提出了她对牧草的要求:第i{i}头奶牛要求她的食物每份的价钱不低于Ai(1<=Ai<=1,000,000,000){A_i(1 <= A_i <= 1,000,000,000),}并且鲜嫩程度不能低于Bi(1<=Bi<=1,000,000,000){B_i(1 <= B_i <= 1,000,000,000)}

商店里供应M(1<=M<=100,000){M(1 <= M <= 100,000)}种不同的牧草,第i{i }种牧草的定价为Ci(1<=Ci<=1,000,000,000){C_i(1 <= C_i <= 1,000,000,000),}鲜嫩程度为Di(1<=Di<=1,000,000,000){D_i (1 <= D_i <= 1,000,000,000)}

为了显示她们的与众不同,每头奶牛都要求她的食物是独一无二的,也就是说,没有哪两头奶牛会选择同一种食物。 FarmerJohn{Farmer John}想知道,为了让所有奶牛满意,他最少 得在购买食物上花多少钱。

输入格式

1{1}行: 2{2}个用空格隔开的整数:N{N }M{M}

2..N+1{2..N+1}行: 第i+1{i+1}行包含2{2}个用空格隔开的整数:Ai{A_i}Bi{B_i }

N+2..N+M+1{N+2..N+M+1}行: 第j+N+1{j+N+1}行包含2{2}个用空格隔开的整数:Ci{C_i}Di{D_i}

输出格式

1{1}行: 输出1{1}个整数,表示使所有奶牛满意的最小花费。

如果无论如何都无法 满足所有奶牛的需求,输出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

输出样例

12

提示

输出说明:

给奶牛1{1}吃价钱为2{2}2{2}号牧草,奶牛2{2}吃价钱为4{4}3{3}号牧草,奶牛3{3}分到价钱

2{2}6{6}号牧草,奶牛4{4}选择价钱为4{4}7{7}号牧草,这种分配方案的总花费是12{12,}为 所有方案中花费最少的。