Problem: 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

Solution (in CPP):

Solution:
#include <iostream>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <algorithm>
#include <cmath>
#include <cstring>
#include <complex>

using namespace std;

//typedef
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef long long ll;

#define omajinai ios::sync_with_stdio(false);cin.tie(0)

//container util
#define ALL(a)  (a).begin(),(a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define UNIQUE(a)  (a).erase(unique((a).begin(),(a).end()),(a).end())
#define MP make_pair
#define SZ(a) int((a).size())
#define EACH(i,c) for(auto i=(c).begin(); i!=(c).end(); ++i)
#define EXIST(s,e) ((s).find(e)!=(s).end())
#define SORT(c) sort((c).begin(),(c).end())

//repetition
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define REP(i,n)  FOR(i,0,n)
#define RFOR(i,b,a) for(int i=(b)-1;i>=(a);--i)
#define RREP(i,n) RFOR(i,n,0)

//clear memory
#define CLR(a) memset((a), 0 ,sizeof(a))

//debug
#define dump(x)  cerr << "[L " << __LINE__ << "] " << #x << " = " << (x) << "\n";

const int _N = 3000,  _M = 1000;
int n,m,v[_N+1],h[_N],t[_M+1],s[_M+1];
int dp[_N+1][_M+1][2]; // [boght items i, 1..][place, 1..][just boght] := max strength
// go next
// or
// buy one more

void smax(int &a, int b){
	a = max(a, b);
}

int main() {
	cin >> n >> m;
	REP(i, n){
		cin >> v[i+1] >> h[i];
		v[i+1]+=v[i];
	}
	REP(i, m){
		cin >> t[i] >> s[i];
	}
	REP(i, n+1)REP(j, m+1)REP(k, 2)dp[i][j][k] = -1;
	dp[0][0][0] = 0;
	REP(j, m){
		REP(i, n+1){
			if(dp[i][j][1]>=0){
				// buy more
				if(i < n && t[j] >= v[i+1])smax(dp[i+1][j][1], dp[i][j][1] + h[i] + abs(h[i] - h[i-1]));
				// go next
				if(s[j] <= dp[i][j][1])smax(dp[i][j+1][0], dp[i][j][1]);
			}
			if(dp[i][j][0]>=0){
				// buy first one
				if(i < n && t[j] >= v[i+1])smax(dp[i+1][j][1], dp[i][j][0] + h[i]);
				// go next
				if(s[j] <= dp[i][j][0])smax(dp[i][j+1][0], dp[i][j][0]);
			}
		}
	}
	REP(i, n+1){
		if(dp[i][m][0] >= 0){
			cout << t[m-1] - v[i] << endl;
			return 0;
		}
	}
	cout << -1 << endl;
}