#include <bits/stdc++.h>
// iostream is too mainstream
#include <cstdio>
// bitch please
#include <iostream>
#include <algorithm>
#include <cstdlib>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <stack>
#include <list>
#include <cmath>
#include <iomanip>
#include <time.h>
#define dibs reserve
#define OVER9000 1234567890123456789LL
#define ALL_THE(CAKE,LIE) for(auto LIE =CAKE.begin(); LIE != CAKE.end(); LIE++)
#define tisic 47
#define soclose 1e-8
#define chocolate win
// so much chocolate
#define patkan 9
#define ff first
#define ss second
#define abs(x) (((x) < 0)?-(x):(x))
#define uint unsigned int
#define dbl long double
#define pi 3.14159265358979323846
using namespace std;
// mylittledoge

using cat = long long;

#ifdef DONLINE_JUDGE
	// palindromic tree is better than splay tree!
	#define lld I64d
#endif

int main() {
	cin.sync_with_stdio(0);
	cin.tie(0);
	cout << fixed << setprecision(10);
	int N, M;
	cin >> N >> M;
	vector< vector<int> > G(N);
	vector<cat> A(N), B(N);
	for(int i = 0; i < N; i++) cin >> A[i] >> B[i];
	for(int i = 0; i < M; i++) {
		int u, v;
		cin >> u >> v;
		G[--u].push_back(--v);
		G[v].push_back(u);
	}
	vector< pair<cat, int> > Vs(N);
	for(int i = 0; i < N; i++) {
		Vs[i].ff = max(0LL, A[i]-B[i]);
		Vs[i].ss = i;
	}
	sort(begin(Vs), end(Vs));

	vector< vector<int> > comp(N);
	for(int i = 0; i < N; i++) comp[i].resize(1, i);
	vector<int> inC(N);
	for(int i = 0; i < N; i++) inC[i] = i;
	vector<bool> live(N, false);
	vector<cat> sumB(N, 0), W(N);
	cat ans = 0;

	for(int i = 0; i < N; i++) {
		int c = Vs[i].ss;
		vector<int> comp_adj;
		ALL_THE(G[c], it) if(live[*it])
			comp_adj.push_back(inC[*it]);
		sort(begin(comp_adj), end(comp_adj));
		auto cae = unique(begin(comp_adj), end(comp_adj));
		int sz = cae - begin(comp_adj);
		comp_adj.resize(sz);

		// aspon A[c] + sumB[susedia okrem j]: viem sa pohybovat hocikde
		// aspon B[c] + sumB[susedia okrem j] + W[j]: viem vyplatit j, c
		// viem vyplatit zvysne? w (>= W1) -> w-S1 (>= W2), w >= max(W1, W2+S1)  //  w (>= W2) -> w-S2 (>= W1), w >= max(W2, W1+S2)
		cat s = 0, m = 0;
		for(int k = 0; k < sz; k++) {
			s += sumB[comp_adj[k]];
			m = max(m, W[comp_adj[k]]);
		}
		W[c] = max(m, max(A[c]+s, B[c]+s));

		if(sz > 1) for(int j = 0; j < sz; j++) {
			s -= sumB[comp_adj[j]];
			cat w_mi = max(A[c]+s, B[c]+s+W[comp_adj[j]])-1, w_mx = W[c];
			if(w_mx <= w_mi+1) {
				s += sumB[comp_adj[j]];
				continue;
			}
			vector< pair<cat, cat> > Vs;
			for(int k = 0; k < sz; k++)
				if(k != j) Vs.push_back(make_pair(W[comp_adj[k]], sumB[comp_adj[k]]));
			sort(begin(Vs), end(Vs));
			vector<bool> vis(sz-1);
			int a = sz-1;
			while(w_mx-w_mi > 1) {
				cat w_cur = (w_mi + w_mx) / 2;
				bool ok = true;
				for(int l = sz-2; l >= 0; l--) {
					if(vis[l]) continue;
					if(Vs[l].ff > w_cur) {
						ok = false;
						break;
					}
					a = min(a, l-1);
					if(a >= 0 && Vs[a].ff > w_cur-Vs[l].ss) {
						vis[a] = true;
						w_cur -= Vs[a].ss;
						a--;
						continue;
					}
					vis[l] = true;
					w_cur -= Vs[l].ss;
				}
				if(ok) w_mx = (w_mi + w_mx) / 2;
				else w_mi = (w_mi + w_mx) / 2;
			}
			// cout << j << " " << i << endl;
			W[c] = min(W[c], w_mx);
			s += sumB[comp_adj[j]];
		}
		else {
			W[c] = min(W[c], max(m+B[c], max(A[c], B[c]+s)));
		}

		sumB[c] = B[c];
		for(int j = 0; j < sz; j++) {
			int a = inC[c], b = comp_adj[j];
			if(comp[a].size() > comp[b].size()) swap(a, b);
			ALL_THE(comp[a], it) {
				comp[b].push_back(*it);
				inC[*it] = b;
			}
			sumB[b] += sumB[a];
		}
		ans = W[inC[c]] = W[c];
		live[c] = true;
	}
	cout << ans << "\n";
	return 0;}

// look at my code
// my code is amazing


Measured memory_bytes: 19712