There is a simple undirected graph with N vertices and M edges. The vertices are numbered 1 through N, and the edges are numbered 1 through M. Edge i connects Vertex U_i and V_i. Also, Vertex i has two predetermined integers A_i and B_i. You will play the following game on this graph.

First, choose one vertex and stand on it, with W yen (the currency of Japan) in your pocket. Here, A_s \leq W must hold, where s is the vertex you choose. Then, perform the following two kinds of operations any number of times in any order:

* Choose one vertex v that is directly connected by an edge to the vertex you are standing on, and move to vertex v. Here, you need to have at least A_v yen in your pocket when you perform this move.
* Donate B_v yen to the vertex v you are standing on. Here, the amount of money in your pocket must not become less than 0 yen.



You win the game when you donate once to every vertex. Find the smallest initial amount of money W that enables you to win the game.

Constraints

* 1 \leq N \leq 10^5
* N-1 \leq M \leq 10^5
* 1 \leq A_i,B_i \leq 10^9
* 1 \leq U_i < V_i \leq N
* The given graph is connected and simple (there is at most one edge between any pair of vertices).

Input

Input is given from Standard Input in the following format:


N M
A_1 B_1
A_2 B_2
:
A_N B_N
U_1 V_1
U_2 V_2
:
U_M V_M


Output

Print the smallest initial amount of money W that enables you to win the game.

Examples

Input

4 5
3 1
1 2
4 1
6 2
1 2
2 3
2 4
1 4
3 4


Output

6


Input

5 8
6 4
15 13
15 19
15 1
20 7
1 3
1 4
1 5
2 3
2 4
2 5
3 5
4 5


Output

44


Input

9 10
131 2
98 79
242 32
231 38
382 82
224 22
140 88
209 70
164 64
6 8
1 6
1 4
1 3
4 7
4 9
3 7
3 9
5 9
2 5


Output

582
#include<bits/stdc++.h>
#define ll long long
#define N 100010
#define M 100010
using namespace std;
struct EDGE{
	ll u, v;
	ll Next;
}G[M << 1];
ll Head[N];
ll tot = 0;
inline void Add(ll u, ll v)
{
	++ tot;
	G[tot].u = u;
	G[tot].v = v;
	G[tot].Next = Head[u];
	Head[u] = tot;
}
struct Node{
	ll a, b, num;
}E[N];
inline bool cmp(Node x, Node y)
{
	return x.a - x.b < y.a - y.b;
}
ll f[N];
ll b[N];
ll w[N];
inline ll Get(ll u)
{
	return f[u] == u ? u : f[u] = Get(f[u]);
}
bool vis[N];
ll d[N], top;
int main()
{
	ll n, m;
	scanf("%lld%lld", &n, &m);
	for(ll i = 1; i <= n; ++ i)
		scanf("%lld%lld", &E[i].a, &E[i].b);
	for(ll i = 1; i <= m; ++ i)
	{
		ll u, v;
		scanf("%lld%lld", &u, &v);
		Add(u, v);
		Add(v, u);
	}
	for(ll i = 1; i <= n; ++ i)
	{
		E[i].num = i;
		b[i] = E[i].b;
		f[i] = i;
	}
	sort(E + 1, E + n + 1, cmp);
	for(ll i = 1; i <= n; ++ i)
	{
		vis[E[i].num] = true;
		ll sumb = 0;
		top = 0;
		for(ll j = Head[E[i].num]; j; j = G[j].Next)
		{
			ll v = G[j].v;
			if(! vis[v])
				continue;
			ll fv = Get(v);
			if(fv != E[i].num)
			{
				sumb += b[fv];
				d[++ top] = fv;
				f[fv] = E[i].num;
			}
		}
		b[E[i].num] = sumb + E[i].b;
		w[E[i].num] = 1000000000000000;
		for(ll j = 1; j <= top; ++ j)
			w[E[i].num] = min(w[E[i].num], sumb - b[d[j]] + max(w[d[j]] + E[i].b, E[i].a));
		w[E[i].num] = min(w[E[i].num], sumb + max(E[i].a, E[i].b));
	}
	printf("%lld", w[E[n].num]);
	return 0;
}