题目描述

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

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

问：最少需要花多少钱？

输入格式

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

接下来 $n$ 行，每行两个整数 $a_i$ 和 $b_i$。

接下来 $m$ 行，每行两个整数 $c_j$ 和 $d_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 ⩽ 30$；

30% 的数据：$1 ⩽ n ⩽ 50, 1 ⩽ m ⩽ 100$；

100% 的数据：$1 ⩽ n, m ⩽ 10^5$，$1 ⩽ a_i,b_i,c_j,d_j ⩽ 10^9$。