P10685 [COTS 2024] 兔子 Zečevi

译自 [Izborne Pripreme 2024 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2024/) 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$。

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

#### 样例解释 样例 $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$ | 无额外约束 |