Description

许多人转生到异世界之后都希望成为勇者打倒魔王，只有小黄立志成为异世界第一倒狗。

这不，小黄今天找到了一家偏僻的冒险家协会，里面有不少商品十分便宜，他准备倒卖这些商品来大赚一笔。但小黄太贪婪了，他的空间戒指早就已经被各种以前买的商品塞满了。幸运的是，冒险家协会能够提供空间戒指临时容量扩充服务，总共有 $n$ 种不同的套餐，第 $i$ 个套餐耗费 $a_i$ 金，使空间戒指的容量暂时增加 $b_i$ 单位。所有的这种升级戒指服务都可以重复购买，并且效果可以叠加。小黄可以通过这种暂时的容量来把想倒卖的商品带走。

冒险家协会有 $m$ 个商品，根据小黄顶级商人的判断，其中第 $i$ 个商品能够使小黄赚到 $c_i$ 金的差价，但需要占用空间戒指 $d_i$ 单位容积。

这种临时容量扩充只对小黄今天在这里倒卖装商品有效，因此除非小黄能通过这次倒卖商品赚取更多的利润，他不会愿意将金币花费在购买空间戒指的临时容量扩充服务上。小黄想知道，扣除临时容量扩充的费用，小黄在这个冒险家协会最多能够赚多少金利润。

Format

Input

第一行两个正整数 $n, m\ (1 \leq n, m \leq 1000)$，分别表示升级空间戒指套餐和商品的数量。

接下来 $n$ 行，每行两个正整数 $a_i, b_i\ (1 \leq a_i \leq 10^9, 1 \leq b_i \leq 10^8)$，分别表示第 $i$ 个套餐的价格和能临时增加空间戒指的容量。

接下来 $m$ 行，每行两个正整数 $c_i, d_i\ (1 \leq c_i \leq 10^9, 1 \leq d_i \leq 100)$，分别表示第 $i$ 个商品能倒卖赚到的价格和需要占用空间戒指的容量

Output

一个整数，表示扣除临时容量扩充的费用，小黄在这个冒险家协会最多能赚多少金利润。

Samples

3 1
1000 1
10000 1
100000 1
115514 1

114514

Limitation

1s, 1024KiB for each test case.