Background

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

Please do not abuse the judging system for this problem. Abusing it will result in your account being banned.

Problem Description

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?

Input Format

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 Format

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

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

Hint

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

Translated by ChatGPT 5