Game Strategy

You have found an old board game in the club room of your programming club. It looks interesting, so you decide to play it.

The game consists of M events, and you have to capture event i at time t_i. However, your strength must be at least s_i at that time. Otherwise, the game is over. At the beginning of the game (time 0), your strength is 0, but you can increase it by buying items. Your money is also 0 at the beginning of the game, but it increases by 1 per unit of time.

There are N items on the board, numbered 1 to N. Item i costs v_i, and buying it increases your strength by h_i. You can buy as many items as you want at any time, as long as you have enough money. However, you must choose the item with the lowest number among the remaining items. Each item will be disappeared after it is bought.

You can also buy multiple items in a row at the same time, and get a bonus equal to the sum of the differences in h_i of the adjacent items. For example, if you buy items 1, 2, 3 at the same time, your strength will increase by |h₁ - h₂| + |h₂ - h₃| in addition to h₁ + h₂ + h₃.

You want to maximize the amount of money you have, after capturing all the events.

Make a program to output the maximum amount of money you have after capturing all the events, using the information of items and events given in input.

Input

The input is given in the following format.

N M
v1 h1
v2 h2
:
vN hN
t1 s1
t2 s2
:
tM sM

In the first line, the number of items N (1 ≤ N ≤ 3000) and the number of events M (1 ≤ M ≤ 1000) are given. In the following N lines, the cost v_i and the increase in strength h_i (1 ≤ v_i, h_i ≤ 100000) of the item i are given. In the following M lines, the time t_i and the condition s_i (1 ≤ t_i, s_i ≤ 100000) of the event i are given. However, if i < j, then t_i < t_j. All inputs are given as integers.

Output

Output the maximum amount of money you have in a line. However, if it is not possible to capture the events, output -1.

Sample Input 1

5 4
3 3
2 1
1 5
4 2
2 6
4 1
8 2
10 4
12 17

Sample Output 1

2

Sample Input 2

5 4
3 3
2 1
1 5
4 2
2 6
4 1
8 2
10 4
12 30 

Sample Output 2

-1

---