Game Strategy

You found an old board game in your programming department's room. It looks interesting so I decided to play with it.

This game consists of M events and you must capture event i at time ti. However, at that time your strength must be si or better, and if you can't be si or better, the game is over. Your strength is 0 at the start of the game (time 0), but you can increase your strength by buying items. Your money at the start of the game is 0, but it increases by 1 per unit time.

The board is ordered with N items each numbered from 1 to N, item i is priced at vi, and purchasing it will increase your strength hi. You can buy as many items as you like at any time if you have enough money, but you must choose the remaining items in ascending order of number. Each item disappears once purchased.

You can also buy multiple items in a row at the same time, and at this time you can get the sum of the hi differences of adjacent items as a bonus. For example, if you buy items 1, 2 and 3 at the same time at a certain time, your strength will increase by | h1 --h2 | + | h2 --h3 | in addition to h1 + h2 + h3.

You want to maximize your money after capturing all the events.

Create a program that inputs item information and event information and outputs the maximum amount of money you have after capturing all the events.

Input

The input is given in the following format.

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

The first line gives the number of items N (1 ≤ N ≤ 3000) and the number of events M (1 ≤ M ≤ 1000). The following N lines give the price vi of item i and the amount of increase in strength hi (1 ≤ vi, hi ≤ 100000). The following M line is given the time ti of event i and the condition si (1 ≤ ti, si ≤ 100000). However, when i <j, ti <tj. All inputs are given as integers.

Output

Output the maximum value of money in your possession on one line. However, if it cannot be captured, "-1" is output.

Examples

Input

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

Output

2

Input

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

Output

-1

inputFormat

inputs item information and event information and

outputFormat

outputs the maximum amount of money you have after capturing all the events.

Input

The input is given in the following format.

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

The first line gives the number of items N (1 ≤ N ≤ 3000) and the number of events M (1 ≤ M ≤ 1000). The following N lines give the price vi of item i and the amount of increase in strength hi (1 ≤ vi, hi ≤ 100000). The following M line is given the time ti of event i and the condition si (1 ≤ ti, si ≤ 100000). However, when i <j, ti <tj. All inputs are given as integers.

Output

Output the maximum value of money in your possession on one line. However, if it cannot be captured, "-1" is output.

Examples

Input

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

Output

2

Input

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

Output

-1

样例

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

-1