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>
using namespace std;

typedef long long lint;
typedef long double louble;

template<typename T1,typename T2> inline T1 max(T1 a,T2 b){return a<b?b:a;}
template<typename T1,typename T2> inline T1 min(T1 a,T2 b){return a<b?a:b;}

const char lf = '\n';

namespace ae86
{
	const int bufl = 1<<15;

	char buf[bufl],*s=buf,*t=buf;

	inline int fetch()
	{
		if(s==t){t=(s=buf)+fread(buf,1,bufl,stdin);if(s==t)return EOF;}
		return *s++;
	}

	inline int ty()
	{
		int a=0,b=1,c=fetch();
		while(!isdigit(c))b^=c=='-',c=fetch();
		while(isdigit(c))a=a*10+c-48,c=fetch();
		return b?a:-a;
	}
}
using ae86::ty;

const int _ = 100007;

vector<int> e[_];
inline void adde(int a,int b){e[a].emplace_back(b);}
inline void addde(int a,int b){adde(a,b),adde(b,a);}

int bfa[_];
int findbfa(int x){return bfa[x]==x?x:bfa[x]=findbfa(bfa[x]);}

int n,m,ps[_];bool ed[_]={0};
lint lim[_],los[_],res[_],slos[_]={0},f[_];

int main()
{
	ios::sync_with_stdio(0),cout.tie(nullptr);

	n=ty(),m=ty();
	for(int i=1;i<=n;i++)lim[i]=ty(),los[i]=ty(),res[i]=max(lim[i]-los[i],0);
	for(int i=1,a,b;i<=m;i++)a=ty(),b=ty(),addde(a,b);

	for(int i=1;i<=n;i++)ps[i]=i;
	sort(ps+1,ps+n+1,[](int a,int b){return res[a]<res[b];});

	for(int i=1;i<=n;i++)bfa[i]=i,slos[i]=los[i],f[i]=res[i];
	for(int i=1;i<=n;i++)
	{
		int a=ps[i];ed[a]=1;
		for(auto b:e[a])
		{
			if(!ed[b])continue;
			int aa=findbfa(a),bb=findbfa(b);
			if(aa==bb)continue;
			bfa[bb]=aa,slos[aa]+=slos[bb];
			f[aa]=min(f[aa],max(f[bb],res[aa]-slos[bb]));
		}
	}

	cout<<slos[findbfa(1)]+f[findbfa(1)]<<lf;
	
	return 0;
}
