题目背景

译自 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$。

子任务编号	分值	约束
$1$	$9$	$N=1$
$2$	$12$	$M=1$
$3$	$26$	$N,M\le 1\, 000$
$4$	$34$	$N,Q\le 50\, 000$
$5$	$19$	无额外约束