当前没有测试数据。

题目描述

某公司正在为一批项目工程采购设备。每个项目都对设备的价格和性能有明确要求。设备服务商有 $M$ 台设备可供选择，其中第 $i$ 台设备的价格为 $P_i$，性能指数为 $Q_i$。

公司有 $N$ 个项目，其中第 $i$ 个项目要求所购买的设备的价格不能低于 $L_i$，性能指数不能低于 $C_i$。为了节约成本，公司希望以最少的采购费用采购设备，并满足所有项目的采购需求。

请你编程帮助公司计算出最小的采购费用，如果无法满足所有项目的需求，输出 -1。

输入格式

第一行包含两个整数 $N$ 和 $M$，分别表示项目数量和设备数量。

接下来的 $N$ 行，每行包含两个整数 $L_i$ 和 $C_i$，分别表示第 $i$ 个项目对设备价格和性能指数的最低要求。

接下来的 $M$ 行，每行包含两个整数 $P_i$ 和 $Q_i$，分别表示第 $i$ 台设备的价格和性能指数。

输出格式

输出一个整数，表示能够满足所有项目需求的最小设备采购总费用。如果无法满足所有项目需求，请输出 -1。

样例

输入

3 5
10 10
20 30
10 40
30 10
20 20
40 30
50 20
50 40

输出

110

数据范围

对于 $60\%$ 的数据，满足 $1 \le N \le 5000$，$1 \le M \le 5000$。

对于 $100\%$ 的数据，满足 $1 \le N \le 10^5$，$1 \le M \le 10^5$，$1 \le L_i, C_i, P_i, Q_i \le 10^9$。