{"raw_statement":[{"iden":"background","content":"译自 [Izborne Pripreme 2024 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2024/) D2T3。$\\texttt{8s,512M}$。\n\n**请不要滥用本题评测。滥用本题评测将被封号。**"},{"iden":"statement","content":"\n数轴上有 $N$ 只兔子，第 $i$ 只兔子位于 $x_i$，起初，第 $i$ 只兔子的能量为 $p_i$。\n\n每秒钟会发生如下的事件：\n\n- 若存在至少一只兔子的能量为 $0$，则过程结束。\n- 否则，每只兔子向右跳跃一个单位长度，同时能量减少 $1$。\n\n数轴上分布着 $M$ 根胡萝卜，第 $i$ 根胡萝卜位于位置 $y_i$，质量为 $t_i$ 千克。当某只兔子的位置上有胡萝卜时，它可以选择吃 $a$ 千克的胡萝卜，其中 $a\\in [0, y]$，其中 $y$ 为胡萝卜的质量。吃掉 $a$ 千克的胡萝卜后，兔子的能量增加 $a$，胡萝卜的质量减少 $a$。\n\n显然兔子一旦停止跳跃，就再也不会跳跃了。在最优的情况下，兔子最多能跳跃多少秒？"},{"iden":"input","content":"\n第一行，两个整数 $N,M$，含义见题面。\n\n接下来 $N$ 行，第 $i$ 行两个整数 $x_i,p_i$；\n\n接下来 $M$ 行，第 $i$ 行两个整数 $y_i,t_i$。\n"},{"iden":"output","content":"\n输出一行一个整数，表示最优情况下的答案。"},{"iden":"note","content":"\n#### 样例解释\n\n样例 $1$ 解释：\n\n我们用二元组 $(x_i,p_i)$ 表示兔子的位置和能量。\n\n跳跃三次后，三只兔子的状态分别为 $(5,1),(10,0),(6,2)$。第二只兔子吃掉 $2$ 千克的胡萝卜，状态变为 $(5,1),(10,2),(6,2)$。\n\n接下来一次跳跃之后，三只兔子的状态分别为 $(6,0),(11,1),(7,1)$。第一只兔子吃掉 $3$ 千克胡萝卜，状态变为 $(6,3),(11,1),(7,1)$。\n\n接下来一次跳跃之后，三只兔子的状态分别为 $(7,2),(12,0),(8,0)$。由于第二只兔子吃不到胡萝卜，所以跳跃过程终止。\n\n可以证明这是最优的答案。\n\n#### 数据范围\n\n对于 $100\\%$ 的数据，保证： \n\n- $1\\le N,M\\le  10^5$；\n- $0\\le x_i,y_i\\le 10^9$；\n- $0\\le p_i,t_i\\le 10^9$。\n\n| 子任务编号 | 分值 | 约束  |\n|:-----:|:------:|:-------:|\n| $1$  | $9$  | $N=1$   |\n| $2$  | $12$  | $M=1$  |\n| $3$  | $26$  | $N,M\\le 1\\, 000$ |\n| $4$  | $34$  | $N,Q\\le 50\\, 000$ |\n| $5$  | $19$  | 无额外约束 |\n"}],"translated_statement":null,"sample_group":[["3 5\n2 4\n7 3\n9 5\n3 2\n8 1\n10 2\n6 3\n1 3","5"],["5 1\n2 6\n3 7\n5 4\n1 10\n7 2\n8 27","11"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}