在数轴上有 $N$ 只兔子，第 $i$ 只兔子位于位置 $x_i$，初始能量为 $p_i$。 每秒钟会发生以下情况：如果所有兔子都至少有 1 单位能量，它们会向右跳跃 1 个单位距离，并消耗 1 单位能量。如果至少有一只兔子的能量为 0，所有兔子将永远停止跳跃。

胡萝卜也位于同一数轴上，第 $i$ 个胡萝卜位于位置 $y_i$，重量为 $t_i$ 千克。当兔子到达胡萝卜所在的位置时，它可以吃掉 $a$ 千克该胡萝卜，其中 $a$ 是一个介于 0 和该胡萝卜当前重量之间的整数。吃掉后，该兔子的能量增加 $a$，胡萝卜的重量减少 $a$ 千克。

请确定在最优策略下，兔子最多能跳跃多少秒。

输入格式

第一行包含两个自然数 $N$ 和 $M$，分别表示兔子的数量和胡萝卜的数量。

接下来的 $N$ 行，每行包含两个整数 $x_i$ 和 $p_i$，分别表示第 $i$ 只兔子的初始位置和初始能量。

接下来的 $M$ 行，每行包含两个整数 $y_i$ 和 $t_i$，分别表示第 $i$ 个胡萝卜的位置和初始重量。

输出格式

输出兔子最多能跳跃的秒数。

数据范围

在所有子任务中，满足 $1 \le N, M \le 10^5$，$0 \le x_i, y_i \le 10^9$，$0 \le p_i, t_i \le 10^9$。没有两只兔子位于同一位置，也没有两个胡萝卜位于同一位置。没有兔子与任何胡萝卜的初始位置相同。

样例

输入 1

3 5
2 4
7 3
9 5
3 2
8 1
10 2
6 3
1 3

输出 1

5

输入 2

5 1
2 6
3 7
5 4
1 10
7 2
8 27

输出 2

11

说明

第一个样例的解释： 在前三次跳跃后，兔子的能量分别为 1、0 和 2。第二只兔子现在位于一个重量为 2 的胡萝卜位置，它可以将其全部吃掉，从而使它的能量变为 2。兔子现在可以再次跳跃一次，之后它们的能量变为 0、1 和 1。第一只兔子现在位于位置 6，那里有一个重量为 3 的胡萝卜。吃掉胡萝卜后，兔子的能量变为 3、1 和 1，因此它们可以再跳跃一次。总共跳跃次数为 5 次。可以证明兔子不可能跳跃 6 次。