There are $N$ rabbits on a number line. The $i$-th rabbit is at position $x_i$ and initially has $p_i$ energy. Every second, the following happens: if all rabbits have at least one unit of energy, they jump one unit to the right and consume one unit of energy. If at least one rabbit has zero energy, they stop jumping forever.
Carrots. Carrots are also on the same number line. The $i$-th carrot is at position $y_i$ and weighs $t_i$ kilograms. When a rabbit reaches a position where a carrot is located, it can eat $a$ kilograms of that carrot, where $a$ is an integer between $0$ and the weight of that carrot. After doing so, that rabbit's energy increases by $a$, and the weight of that carrot decreases by $a$ kilograms.
Determine the maximum number of seconds the rabbits can jump, assuming they eat the carrots optimally.
Input
The first line contains natural numbers $N$ and $M$, the number of rabbits and the number of carrots.
The next $N$ lines each contain two numbers. The $i$-th of these lines contains $x_i$ and $p_i$, the initial position and energy of the $i$-th rabbit.
The next $M$ lines each contain two numbers. The $i$-th of these lines contains $y_i$ and $t_i$, the position and initial weight of the $i$-th carrot.
Output
Output the maximum number of seconds the rabbits can jump.
Subtasks
In all subtasks, $1 \le N, M \le 10^5$, $0 \le x_i, y_i \le 10^9$, and $0 \le p_i, t_i \le 10^9$. No two rabbits and no two carrots are at the same position. No rabbit is at the same initial position as any carrot.
| Subtask | Points | Constraints |
|---|---|---|
| 1 | 9 | $N = 1$ |
| 2 | 12 | $M = 1$ |
| 3 | 26 | $N, M \le 1000$ |
| 4 | 34 | $N, M \le 50000$ |
| 5 | 19 | No additional constraints. |
Examples
Input 1
3 5 2 4 7 3 9 5 3 2 8 1 10 2 6 3 1 3
Output 1
5
Note 1
After the first three jumps, the rabbits have energies 1, 0, and 2, respectively. The second rabbit is now at a position where there is a carrot of weight 2, so it can eat the whole thing, making its energy 2. The rabbits can now make another jump, after which their energies become 0, 1, and 1. The first rabbit is now at position 6, where there is a carrot of weight 3. After eating the carrot, the rabbits have energies 3, 1, and 1, so they can make one more jump. The total number of jumps made is five. It is possible to show that it is impossible for the rabbits to make six jumps.
Input 2
5 1 2 6 3 7 5 4 1 10 7 2 8 27
Output 2
11