#540. 购物

购物

题目描述

有 m 件商品,第 j 件商品的价格为 cj, 体积为 dj。

要从中选购 n 件商品,要求选出的第 i 件商品的价格不小于 ai, 体积不小于 bi。

问:最少需要花多少钱?

输入格式

第一行:两个整数 nn 和 mm。

接下来 nn 行,每行两个整数 aia_i 和 bib_i。

接下来 mm 行,每行两个整数 cjc_j 和 djd_j。

输出格式

一个整数,表示最少花费。如果不存在满足要求的购买方案,则输出 -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

数据范围

20% 的数据:1⩽n⩽10,1⩽m⩽301 ⩽ n ⩽ 10, 1 ⩽ m ⩽ 30;

30% 的数据:1⩽n⩽50,1⩽m⩽1001 ⩽ n ⩽ 50, 1 ⩽ m ⩽ 100;

100% 的数据:1⩽n,m⩽1051 ⩽ n, m ⩽ 10^5,1⩽ai,bi,cj,dj⩽1091 ⩽ a_i,b_i,c_j,d_j ⩽ 10^9。