P10685 [COTS 2024] Rabbits Zečevi

Translated from [Izborne Pripreme 2024 (Croatian IOI/CEOI Team Selection)](https://hsin.hr/pripreme2024/) D2T3。$\texttt{8s,512M}$。 **Please do not abuse the judging system for this problem. Abusing it will result in your account being banned.**

There are $N$ rabbits on the number line. Rabbit $i$ is at position $x_i$. Initially, rabbit $i$ has energy $p_i$. Every second, the following events happen: - If there exists at least one rabbit whose energy is $0$, the process ends. - Otherwise, every rabbit jumps $1$ unit to the right, and its energy decreases by $1$. There are $M$ carrots on the number line. Carrot $i$ is at position $y_i$ and has mass $t_i$ kilograms. When a rabbit is on a position with a carrot, it may choose to eat $a$ kilograms of that carrot, where $a\in [0, y]$, and $y$ is the carrot's mass. After eating $a$ kilograms, the rabbit's energy increases by $a$, and the carrot's mass decreases by $a$. Clearly, once the rabbits stop jumping, they will never jump again. Under optimal decisions, what is the maximum number of seconds the rabbits can keep jumping?

The first line contains two integers $N,M$, as described above. The next $N$ lines each contain two integers $x_i,p_i$. The next $M$ lines each contain two integers $y_i,t_i$.

Output one line with one integer, representing the answer under optimal decisions.

#### Sample Explanation Explanation for sample $1$: We use a pair $(x_i,p_i)$ to represent a rabbit's position and energy. After three jumps, the three rabbits are in states $(5,1),(10,0),(6,2)$. The second rabbit eats $2$ kilograms of carrot, becoming $(5,1),(10,2),(6,2)$. After the next jump, the three rabbits are in states $(6,0),(11,1),(7,1)$. The first rabbit eats $3$ kilograms of carrot, becoming $(6,3),(11,1),(7,1)$. After the next jump, the three rabbits are in states $(7,2),(12,0),(8,0)$. Since the second rabbit cannot eat any carrot, the jumping process terminates. It can be proven that this is the optimal answer. #### Constraints For $100\%$ of the testdata, it is guaranteed that: - $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$。 | Subtask ID | Score | Constraints | |:-----:|:------:|:-------:| | $1$ | $9$ | $N=1$ | | $2$ | $12$ | $M=1$ | | $3$ | $26$ | $N,M\le 1\, 000$ | | $4$ | $34$ | $N,Q\le 50\, 000$ | | $5$ | $19$ | No additional constraints | Translated by ChatGPT 5