Castle

Bob is a big fan of constructions and in order to get new prizes, he decided to study the art of building sand castles in order to win the annual summer sand castle building competition.

While studying techniques for building the castles, he observed an interesting feature of building such a construction. Namely, once in a while, a wave comes and destroys some, if not all of the castle and the job has to be partly (or even fully) done again.

Now, in order to experiment various strategies, he has now got $n$ different techniques of building and he also knows when the next $q$ waves will come.

For each technique, he knows how long it takes him to fully implement it and also how many hit points it adds to the castle. Since he's a celebrity and therefore very rich, he can afford to use each technique as many times as he wants.

For each wave, we know its power, a number $q_i$ and the wave will remove $q_i$ hit points from the castle or it fully destroys it, if the number becomes $0$ or smaller, and in that case, the value of the HP becomes $0$.

Now Bob wants to know how to use his techniques, one at a time, such that the minimum number of hit points the castle has after being damaged by each wave is as big as possible.

For example, if these events happen in the following order: $[4, 7, −3, 5, −9, 2, −1]$, the minimum number of hit points will be $min(4 + 7 − 3, 8 + 5 − 9, 4 + 2 − 1) = 4$, where a positive number means a spell was done and a negative number means a wave came.

It is known that if a wave comes at the same time as Bob finishes his technique, the technique is finished first and then the wave comes.

Input

The first line of the input will contain two integers, $n$ and $q$, $(1 ≤ n, q ≤ 1 \ 000)$, representing the number of construction techniques and the number of waves.

On the next $n$ lines we have the description of the construction techniques: on each line, a pair $(t_i, hp_i)$ is presented, such that after $t_i$ seconds, the castle will get extra $hp_i$ ($1 ≤ t_i, hp_i ≤ 10 \ 000$).

On the next $q$ lines we have the description of the waves: on each line, a pair $(t_i, hp_i)$ is presented, such that after $t_i$ seconds, the castle will get $hp_i$ damage $(1 ≤ t_i, hp_i ≤ 10 \ 000)$.

For tests worth $30$ points, $(1 ≤ n, q ≤ 100)$

It is not guaranteed that all the waves come at distinct times.

Output

The output will contain a single integer, representing the maximum number of the minimum value of hit points the castle can have after it was hit by waves (or $0$ if we can't keep it standing no matter what).

Example

stdin

4 3
4 4
3 2
5 7
2 2
5 5
8 2
15 6

stdout

2

Explanation

The techniques will be used in the following order $3, 4, 2, 3$

Wave after $5$ seconds: The hit points will be equal to $7 − 5 = 2$

Wave after $8$ seconds: The hit points will be equal to $2 + 2 − 2 = 2$

Wave after $15$ seconds: The hit points will be equal to $2 + 2 + 7 − 6 = 5$

Therefore, the answer is $2$.