You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

译自 Izborne Pripreme 2024 (Croatian IOI/CEOI Team Selection) D2T3。$\texttt{8s,512M}$。

请不要滥用本题评测。滥用本题评测将被封号。

题目描述

数轴上有 $N$ 只兔子，第 $i$ 只兔子位于 $x_i$，起初，第 $i$ 只兔子的能量为 $p_i$。

每秒钟会发生如下的事件：

• 若存在至少一只兔子的能量为 $0$，则过程结束。
• 否则，每只兔子向右跳跃一个单位长度，同时能量减少 $1$。

数轴上分布着 $M$ 根胡萝卜，第 $i$ 根胡萝卜位于位置 $y_i$，质量为 $t_i$ 千克。当某只兔子的位置上有胡萝卜时，它可以选择吃 $a$ 千克的胡萝卜，其中 $a\in [0, y]$，其中 $y$ 为胡萝卜的质量。吃掉 $a$ 千克的胡萝卜后，兔子的能量增加 $a$，胡萝卜的质量减少 $a$。

显然兔子一旦停止跳跃，就再也不会跳跃了。在最优的情况下，兔子最多能跳跃多少秒？

输入格式

第一行，两个整数 $N,M$，含义见题面。

接下来 $N$ 行，第 $i$ 行两个整数 $x_i,p_i$；

接下来 $M$ 行，第 $i$ 行两个整数 $y_i,t_i$。

输出格式

输出一行一个整数，表示最优情况下的答案。

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

5

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

11

提示

样例解释

样例 $1$ 解释：

我们用二元组 $(x_i,p_i)$ 表示兔子的位置和能量。

跳跃三次后，三只兔子的状态分别为 $(5,1),(10,0),(6,2)$。第二只兔子吃掉 $2$ 千克的胡萝卜，状态变为 $(5,1),(10,2),(6,2)$。

接下来一次跳跃之后，三只兔子的状态分别为 $(6,0),(11,1),(7,1)$。第一只兔子吃掉 $3$ 千克胡萝卜，状态变为 $(6,3),(11,1),(7,1)$。

接下来一次跳跃之后，三只兔子的状态分别为 $(7,2),(12,0),(8,0)$。由于第二只兔子吃不到胡萝卜，所以跳跃过程终止。

可以证明这是最优的答案。

数据范围

对于 $100\%$ 的数据，保证：

• $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$。