Problem Background

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

Do not abuse the judging system for this problem. Abuse will result in account suspension.

Problem Description

There are $N$ rabbits on a number line. The $i$-th rabbit is located at position $x_i$ and initially has energy $p_i$.

Each second, the following events occur:

• If there is at least one rabbit with energy $0$, the process ends.
• Otherwise, each rabbit jumps one unit to the right and its energy decreases by $1$.

There are $M$ carrots distributed on the number line. The $i$-th carrot is at position $y_i$ and has a mass of $t_i$ kilograms. When a rabbit is at a position with a carrot, it can choose to eat $a$ kilograms of the carrot, where $a \in [0, y]$, with $y$ being the mass of the carrot. After eating $a$ kilograms, the rabbit's energy increases by $a$, and the carrot's mass decreases by $a$.

Clearly, once a rabbit stops jumping, it will never jump again. In the optimal scenario, how many seconds can the rabbits jump at most?

Input Format

The first line contains two integers $N, M$, as described in the problem statement.

The next $N$ lines contain two integers each, $x_i, p_i$.

The next $M$ lines contain two integers each, $y_i, t_i$.

Output Format

Output a single integer, the answer in the optimal scenario.

Sample Input and Output

Sample Input #1

3 5
2 4
7 3
9 5
3 2
8 1
10 2
6 3
1 3

Sample Output #1

5

Sample Input #2

5 1
2 6
3 7
5 4
1 10
7 2
8 27

Sample Output #2

11

Notes

Sample Explanation

Sample $1$ Explanation:

We represent the state of a rabbit with a tuple $(x_i, p_i)$.

After three jumps, the states of the three rabbits are $(5, 1), (10, 0), (6, 2)$. The second rabbit eats $2$ kilograms of carrot, changing its state to $(5, 1), (10, 2), (6, 2)$.

After the next jump, the states are $(6, 0), (11, 1), (7, 1)$. The first rabbit eats $3$ kilograms of carrot, changing its state to $(6, 3), (11, 1), (7, 1)$.

After the next jump, the states are $(7, 2), (12, 0), (8, 0)$. Since the second rabbit cannot reach any carrot, the jumping process ends.

It can be proven that this is the optimal answer.

Data Range

For $100\%$ of the data, 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$.

见题面 Input 部分

见题面 Output 部分