题目背景

题目提供者：mdxz114514

题目类型：原创题

个人发布原题：U461224

在冒险湾里，有人遇到麻烦了！但是莱德他是第一次执行任务，他不会预计什么时候完成，请你帮帮他！

题目描述

在这次任务中，有\(n\)只gen（狗）和\(m\)个麻烦。

\(n\)只gen中，第\(i\)只gen可以解决\(a_i\)类型的问题（\(a_i\)不会重复），但是需要花费时间，也要花费\(b_i\)的时间到达现场。

\(m\)个麻烦中，第\(i\)个麻烦的类型是\(c_i\)（\(c_i\)会重复），也就是说，如果一只gen的解决类型等于这个麻烦的类型，那么这只gen可以解决这个麻烦，而要解决麻烦的时间是\(d_i\)。

当所有数据都统计完后，莱德会做操作：

将一只gen命令出发：耗时\(1\)秒

而gen接收命令出发，会按顺序做以下操作：

到达现场：耗时\(b_i\)秒

解决麻烦：移动不耗时间。全都做完后会留在现场

当所有麻烦都被解决掉后就算任务完成，如果有麻烦不能解决，输出-1。

莱德和gen们**可以同时行动**

输入格式

第\(1\)行，\(n\)和\(m\)

接下来\(n\)行，\(a_i\)和\(b_i\)

接下来\(m\)行，\(c_i\)和\(d_i\)

输出格式

任务不能完成输出-1，否则输出完成任务的最小耗时

样例 #1

样例输入 #1

3 3
1 2
2 5
3 8
1 3
2 8
3 5

样例输出 #1

15

样例 #2

样例输入 #2

3 3
1 1
2 1
4 4
1 5
2 1
3 4

样例输出 #2

-1

提示

100%的数据中：\(1 \le n,m \le 10^5\)，\(1 \le a_i,c_i \le 10^5\)，\(1 \le b_i,d_i \le 10^5\)

后续

冒险湾ers: