stablegradients/pie-gem5-bysrc huggingface dataset:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

#define lor(a,b,c) for(register int a=b;a<=c;++a)

#define ror(a,b,c) for(register int a=c;a>=b;--a)

typedef long long ll;



const int N=3e5+5;

const ll MOD=1e9+7;



char s[N]; int n;

ll f[N][3][3],ans;



inline void inc(ll &a,ll b){

	(a+=b)>=MOD?a-=MOD:a;

}



inline void trans(int &a,int &b,int c){

	if(!c){

		++b; if(b>=3) b-=2;

	}

	else{

		if(b) --b;

		else ++a,a=min(a,2);

	}

}



int main(){

	//freopen("test.in","r",stdin);



	scanf("%s",s+1); n=strlen(s+1);

	f[0][0][0]=1ll;

	lor(k,1,n){

		if(s[k]!='0'){

			lor(i,0,2) lor(j,0,2){

				int a=i,b=j; trans(a,b,1);

				inc(f[k][a][b],f[k-1][i][j]);

			}

		}

		if(s[k]!='1'){

			lor(i,0,2) lor(j,0,2){

				int a=i,b=j; trans(a,b,0);

				inc(f[k][a][b],f[k-1][i][j]);

			}			

		}

	}

	lor(i,0,2) lor(j,0,i) inc(ans,f[n][i][j]);

	printf("%lld\n",ans);



	return 0;

}

// Optimized solution to the same problem (faster):
#include<cstdio>

#define p 1000000007

int i,j,_[8][2]={{},{2,3},{4,1},{5,7},{2,2},{6,3},{5,5},{7,7}},dp[2][8];

char s[300005];

int main()

{

	scanf("%s",s+1);

	int*f=dp[0],*g=dp[1],*q;

	for(f[1]=i=1;s[i];i++,q=f,f=g,g=q)for(j=1;j<8;f[j++]=0)if(f[j])s[i]!='1'&&((g[_[j][0]]+=f[j])%=p),s[i]!='0'&&((g[_[j][1]]+=f[j])%=p);

	printf("%d",(f[3]+f[7])%p);

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

using namespace std;

int main()

{

	int w, a, b;

	cin >> w >> a >> b;

	if (b - (a + w)>0)

    cout<< b - (a + w);

	else if ((b + w) >= a) cout << "0";

	else cout <<a - (b + w);

	system("pause");

	return 0;

}

// Optimized solution to the same problem (faster):
#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <string>

#include <cmath>

#include <algorithm>

#include <vector>

#include <map>

#include <queue>

#include <set>

using namespace std;

typedef long long LL;

const int MaxN = 1e5;

const int Inf = 1 << 30;

const LL mod = 1e9 + 7;



int main()

{

	int a,b,w;

	while(~scanf("%d%d%d",&w,&a,&b)){

		if(a > b) swap(a,b);

		a = b - w - a;

		if(a < 0) a = 0;

		printf("%d\n",a);

	}

    return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

#define IN freopen("input.txt","r",stdin);

#define MAX5 100005

#define MAX6 1000005

#define MAX7 1000005

#define sf scanf

#define pf printf

#define pb push_back

#define all(x) x.begin(),x.end()

typedef long long int ll;

int TEST=1,CASE=1;

struct vpair{

    int a;

    int b;

    vpair(int a,int b){this->a=a;this->b=b;}

};

bool cmp(vpair &a,vpair &b){

    if(a.b<b.a)return true;

    else if(a.a==b.a){

        if(a.b<b.a)return true;

        else return false;

    }else return false;

}

int a,b,w;

int main(void){

    cin>>w>>a>>b;

    if(b<=a+w && b>=a){

        cout<<0<<endl;

        return 0;

    }

    if(b>a+w){

        cout<<b-(a+w)<<endl;

        return 0;

    }

    if(b+w>=a && b+w<=a+w){

        cout<<0<<endl;

        return 0;

    }

    if(b+w<a){

        cout<<a-(b+w)<<endl;

        return 0;

    }

    return 0;

}


// Optimized solution to the same problem (faster):
#include<stdio.h>

using namespace std;

int main()

{

   int w,a,b;

   scanf("%d %d %d",&w,&a,&b);



  if(a+w<b)

   {

    printf("%d\n",b-(a+w));

   }



    else if(a>b+w)

    {

      printf("%d\n",a-(b+w));

    }



  else

    {

     printf("0\n");

    }

return 0;

}




// Fastest known solution for this problem:
// Original C++ solution (slower):


#include<iostream>

using namespace std;





int main()

{

   int w,b,c,sum=0,rest=0;

   cin>>w>>b>>c;



   if(c<b && c+w< b)

   {

       cout<<b-(c+w);

   }

   else if(c<b && c+w>=b)

   {

       cout<<0;

   }



   else if(c>b && c>b+w)

   {

       cout<<c-b-w;

   }

   else if(c>b && b+w>=c)

   {

       cout<<0;

   }

   else if(b==c)

   {

       cout<<0;

   }



}


// Optimized solution to the same problem (faster):
#include<stdio.h>

using namespace std;

int main()

{

   int w,a,b;

   scanf("%d %d %d",&w,&a,&b);



  if(a+w<b)

   {

    printf("%d\n",b-(a+w));

   }



    else if(a>b+w)

    {

      printf("%d\n",a-(b+w));

    }



  else

    {

     printf("0\n");

    }

return 0;

}




// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <cmath>

#include <cstdlib>

using namespace std;



int main() {

	int W, a, b;

	cin >> W >> a >> b;

	if(a > b) swap(a, b);

	if (b <= a + W && b + W >= a + W) cout << '0' << endl;

	else {

		if(b > a) cout << b - a - W << endl;

		else cout << a - b - W << endl;

	}

}

// Optimized solution to the same problem (faster):
#include<stdio.h>

using namespace std;

int main()

{

   int w,a,b;

   scanf("%d %d %d",&w,&a,&b);



  if(a+w<b)

   {

    printf("%d\n",b-(a+w));

   }



    else if(a>b+w)

    {

      printf("%d\n",a-(b+w));

    }



  else

    {

     printf("0\n");

    }

return 0;

}




// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

int main() {

    int w, a, b;

scanf("%d %d %d",&w,&a,&b);

    if(b >= a + w) 

	cout<<(b - (a + w));

    else if (b + w <= a) 

	cout<<(a - (b + w));

    else 

	cout<<0;

}

 

// Optimized solution to the same problem (faster):
#include<stdio.h>

using namespace std;

int main()

{

   int w,a,b;

   scanf("%d %d %d",&w,&a,&b);



  if(a+w<b)

   {

    printf("%d\n",b-(a+w));

   }



    else if(a>b+w)

    {

      printf("%d\n",a-(b+w));

    }



  else

    {

     printf("0\n");

    }

return 0;

}




// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<iostream>

using namespace std;

int main(){

   double w,a,b;

   cin>>w>>a>>b;

   if(w+a< b)

      cout<<b-(a+w);

     else if(a> b+w)

       cout<<a-(b+w);

       else 

           cout<<"0";

       



	 	return 0;

}

// Optimized solution to the same problem (faster):
#include<stdio.h>

using namespace std;

int main()

{

   int w,a,b;

   scanf("%d %d %d",&w,&a,&b);



  if(a+w<b)

   {

    printf("%d\n",b-(a+w));

   }



    else if(a>b+w)

    {

      printf("%d\n",a-(b+w));

    }



  else

    {

     printf("0\n");

    }

return 0;

}




// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

int w,a,b,aww;

int main () {

cin >> w >> a >> b;

	if (a > b) {

		aww= a - (b+w);

	}

	else {

		aww= b - (a+w);

	}

	if (aww <= 0) {

		cout << 0 << endl;

	}

	else {

		cout << aww << endl;

	}

}

// Optimized solution to the same problem (faster):
#include<stdio.h>

using namespace std;

int main()

{

   int w,a,b;

   scanf("%d %d %d",&w,&a,&b);



  if(a+w<b)

   {

    printf("%d\n",b-(a+w));

   }



    else if(a>b+w)

    {

      printf("%d\n",a-(b+w));

    }



  else

    {

     printf("0\n");

    }

return 0;

}




// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>



using namespace std;



int main()

{

    int w{};

    int a{};

    int b{};

    cin >> w >> a >> b;

    int ans{max(a,b)-(min(a,b)+w)};

    if (ans<=0)

        cout << 0<< endl;

    else

        cout << ans;

    return 0;

}


// Optimized solution to the same problem (faster):
#include<stdio.h>

using namespace std;

int main()

{

   int w,a,b;

   scanf("%d %d %d",&w,&a,&b);



  if(a+w<b)

   {

    printf("%d\n",b-(a+w));

   }



    else if(a>b+w)

    {

      printf("%d\n",a-(b+w));

    }



  else

    {

     printf("0\n");

    }

return 0;

}




// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <iostream>

#include <vector>

#include <cmath>

#include <string>

#include <algorithm>

#include <iomanip>

#include <map>

#include <bitset>

#include <cstdio>

#include <set>

#include <stack>

#include <queue>

#include <cassert>

#include <numeric>

#define rep(i,n) Rep(i,0,n)

#define Rep(i,k,n) for(int i=k ; i<n ; i++)

#define rep1(i,n) for(int i=1 ; i<=n ; i++)

#define Rep1(i,k,n) for(int i=k ; i<=n ; i++)

#define vi vector<int>

#define vii vector<vector<int>>

#define mii map<int,int>

#define Sort(v) sort(v.begin(),v.end())

#define Reverse(v) reverse(v.begin(),v.end())

#define ALL(a)  (a).begin(),(a).end()

#define pb push_back

//#define int ll

typedef long long ll;



const int md = 1000000007;

const int INF = 1<<30;

using namespace std;



double inverse(int x){

    return (1.0)/x;

}





int main(){

    int k; cin >> k;

    int a = k/2;

    cout << a*(k-a) << endl;

}


// Optimized solution to the same problem (faster):
#include<cstdio>

using namespace std;

int main(){

	int k;

	scanf("%d",&k);

	int sum=k/2;

	printf("%d\n",sum*(k-sum));

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

#define fi first

#define se second

#ifdef CX_TEST

#define Debug printf

#else

#define Debug(...)

#endif

#define LL long long

using namespace std;

typedef pair<int, int> P;

const int maxn = 1e5 + 5;



int a[maxn], b[maxn], c[maxn], p[maxn];

LL s[maxn], d[maxn];

bool vis[maxn];

vector<int> g[maxn];



bool cmp(const int x, const int y) {

    return a[x] < a[y];

}



int ff(int x) {

    if(p[x] != x) p[x] = ff(p[x]);

    return p[x];

}



int main() {

#ifdef CX_TEST

    freopen("E:\\program--GG\\test_in.txt", "r", stdin);

#endif

    int n, m, i, j, u, v;

    scanf("%d%d", &n, &m);

    for(i = 1;i <= n; i++) {

        scanf("%d%d", &a[i], &b[i]);

        a[i] = max(a[i] - b[i], 0);

        s[i] = b[i];

        d[i] = a[i];

    }

    for(i = 0;i < m; i++) {

        scanf("%d%d", &u, &v);

        g[u].push_back(v);

        g[v].push_back(u);

    }

    for(i = 1;i <= n; i++) c[i] = i;

    for(i = 1;i <= n; i++) p[i] = i;

    sort(c + 1, c + n + 1, cmp);

    for(i = 1;i <= n; i++) {

        j = c[i];

        vis[j] = 1;

        for(auto e:g[j]) {

            if(vis[e]) {

                u = ff(j), v = ff(e);

                if(u != v) {

                    s[u] += s[v];

                    p[v] = u;

                    d[u] = min(d[u], d[v] + max(0LL, a[u] - d[v] - s[v]));

                }

            }

        }

    }

    cout << s[c[n]] + d[c[n]] << endl;

    return 0;

}


// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

typedef long long LL;

using namespace std;

const int N=1e5+5;

int n,m,fa[N],p[N];

LL sum[N],f[N],a[N],b[N];

int head[N],ce;

bool vis[N];

struct edge{int to,nxt;} e[N<<1];

bool cmp(int x,int y) {return a[x]<a[y];}

void adde(int x,int y) {e[++ce].to=y,e[ce].nxt=head[x],head[x]=ce;}

int find(int x)

{

	if(x==fa[x]) return x;

	return fa[x]=find(fa[x]);

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;++i)

	{

		scanf("%lld%lld",&a[i],&b[i]);

		a[i]=max(a[i]-b[i],0ll);

		p[i]=fa[i]=i,f[i]=a[i],sum[i]=b[i];

	}

	for(int i=1;i<=m;++i)

	{

		int x,y;

		scanf("%d%d",&x,&y);

		adde(x,y); adde(y,x);

	}

	sort(p+1,p+n+1,cmp);

	for(int i=1;i<=n;++i)

	{

		int u=p[i]; vis[u]=1;

		for(int j=head[u];j;j=e[j].nxt)

		{

			int v=e[j].to;

			if(!vis[v]) continue;

			int x=find(u),y=find(v);

			if(x!=y)

			{

				fa[y]=x,sum[x]+=sum[y];

				f[x]=min(f[x],max(f[y],a[x]-sum[y]));

			}

		}

	}

	printf("%lld",f[find(1)]+sum[find(1)]);

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include<bits/stdc++.h>

using namespace std;

#define ll long long

const int maxn=1e5+7;

bool vis[maxn];

int a[maxn],b[maxn],p[maxn],fa[maxn];

ll c[maxn];

ll dp[maxn],sum[maxn];

struct Edge{

	int nxt,to;

}G[maxn<<1],T[maxn<<1];

int bG=0,hG[maxn],bT=0,hT[maxn<<1];

void addG(int x,int y){

	G[bG].nxt=hG[x];G[bG].to=y;hG[x]=bG++;

	G[bG].nxt=hG[y];G[bG].to=x;hG[y]=bG++;

}

void addT(int x,int y){

	T[bT].nxt=hT[x];T[bT].to=y;hT[x]=bT++;

	T[bT].nxt=hT[y];T[bT].to=x;hT[y]=bT++;

}

bool cmp(int x,int y){

	return c[x]<c[y];

}

void dfs(int v,int p){

	sum[v]=b[v];

	for (int i=hT[v];i!=-1;i=T[i].nxt){

		int u=T[i].to;

		if (u==p) continue;

		dfs(u,v);

		sum[v]+=sum[u];

	}

	dp[v]=sum[v]+c[v];

	for (int i=hT[v];i!=-1;i=T[i].nxt){

		int u=T[i].to;

		if (u==p) continue;

		dp[v]=min(dp[v],sum[v]-sum[u]+max(dp[u],c[v]));

	}

}

int Get(int x){

	if (fa[x]==x) return x;

	fa[x]=Get(fa[x]);return fa[x];

}

int main(){

	memset(hG,-1,sizeof(hG));

	memset(hT,-1,sizeof(hT));

	int n,m;scanf("%d%d",&n,&m);

	for (int i=0;i<n;i++){

		scanf("%d%d",a+i,b+i);

		c[i]=max(a[i]-b[i],0);

		p[i]=i;fa[i]=i;

	}

	for (int i=0;i<m;i++){

		int u,v;scanf("%d%d",&u,&v);u--;v--;addG(u,v);

	}

	sort(p,p+n,cmp);

	for (int i=0;i<n;i++){

		int v=p[i];

		vis[v]=true;

		for (int e=hG[v];e!=-1;e=G[e].nxt){

			int u=G[e].to;

			int fu=Get(u);

			if (vis[u] && v!=fu){

				fa[fu]=v;

				addT(fu,v);

			}

		}

	}

	dfs(p[n-1],-1);

	printf("%lld\n",dp[p[n-1]]);

	return 0;

}

// Optimized solution to the same problem (faster):
#include<bits/stdc++.h>

typedef long long LL;

using namespace std;

const int N=1e5+5;

int n,m,fa[N],p[N];

LL sum[N],f[N],a[N],b[N];

int head[N],ce;

bool vis[N];

struct edge{int to,nxt;} e[N<<1];

bool cmp(int x,int y) {return a[x]<a[y];}

void adde(int x,int y) {e[++ce].to=y,e[ce].nxt=head[x],head[x]=ce;}

int find(int x)

{

	if(x==fa[x]) return x;

	return fa[x]=find(fa[x]);

}

int main()

{

	scanf("%d%d",&n,&m);

	for(int i=1;i<=n;++i)

	{

		scanf("%lld%lld",&a[i],&b[i]);

		a[i]=max(a[i]-b[i],0ll);

		p[i]=fa[i]=i,f[i]=a[i],sum[i]=b[i];

	}

	for(int i=1;i<=m;++i)

	{

		int x,y;

		scanf("%d%d",&x,&y);

		adde(x,y); adde(y,x);

	}

	sort(p+1,p+n+1,cmp);

	for(int i=1;i<=n;++i)

	{

		int u=p[i]; vis[u]=1;

		for(int j=head[u];j;j=e[j].nxt)

		{

			int v=e[j].to;

			if(!vis[v]) continue;

			int x=find(u),y=find(v);

			if(x!=y)

			{

				fa[y]=x,sum[x]+=sum[y];

				f[x]=min(f[x],max(f[y],a[x]-sum[y]));

			}

		}

	}

	printf("%lld",f[find(1)]+sum[find(1)]);

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;

#define MAXN 100000

#define ll long long

#define rint register int

inline int read(){int r;int s=0,c;for(;!isdigit(c=getchar());s=c);for(r=c^48;isdigit(c=getchar());(r*=10)+=c^48);return s^45?r:-r;}

vector<int> e[MAXN+5], g[MAXN+5]; int A[MAXN+5], B[MAXN+5], fa[MAXN+5], rk[MAXN+5] ,o[MAXN+5], n, m; ll f[MAXN+5], s[MAXN+5];

inline bool cmp(int i, int j){return A[i]<A[j];} inline int getf(int x){return x^fa[x]?fa[x]=getf(fa[x]):x;}

ll DP(int p){for(auto v:g[p]) f[p] = min(f[p],max((ll)A[o[p]],DP(v))-s[v]), s[p] += s[v]; return f[p] += s[p];}

int main()

{

	n = read(); m = read(); for(rint i = 1; i <= n; A[i] = read(), B[i] = read(), A[i] = max(A[i]-B[i],0), fa[i] = o[i] = i, i++); sort(o+1,o+n+1,cmp);

	for(rint i = 1; i <= n; rk[o[i]] = i, f[i] = A[o[i]], s[i] = B[o[i]], i++); for(rint a, b; m--; a = rk[read()], b = rk[read()], e[a].push_back(b), e[b].push_back(a));

	for(rint u = 1, U, V; u <= n; u++) for(auto v:e[u]) v<u&&(V=getf(v))^(U=getf(u))?g[U].push_back(V),fa[V]=U:0; printf("%lld\n",DP(getf(1))); return 0;

}

// Optimized solution to the same problem (faster):
#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cstring> 

#include <cmath> 

#include <algorithm>

#include <vector> 

using namespace std; 

inline int gi() {

    register int data = 0, w = 1;

    register char ch = 0;

    while (!isdigit(ch) && ch != '-') ch = getchar(); 

    if (ch == '-') w = -1, ch = getchar(); 

    while (isdigit(ch)) data = 10 * data + ch - '0', ch = getchar(); 

    return w * data; 

} 

const int MAX_N = 1e5 + 5; 

int N, M, a[MAX_N], b[MAX_N], p[MAX_N]; 

int pa[MAX_N]; 

int getf(int x) { while (x != pa[x]) x = pa[x] = pa[pa[x]]; return x; } 

vector<int> G[MAX_N]; 

long long f[MAX_N], sum[MAX_N];

bool vis[MAX_N]; 

int main () { 

	N = gi(), M = gi();

	for (int i = 1; i <= N; i++) { 

		a[i] = gi(), b[i] = gi(); 

		a[i] = max(a[i] - b[i], 0);

		p[i] = i, pa[i] = i; 

	} 

	sort(&p[1], &p[N + 1], [](const int &l, const int &r) { return a[l] < a[r]; } ); 

	for (int i = 1; i <= M; i++) { 

		int u = gi(), v = gi(); 

		G[u].push_back(v), G[v].push_back(u); 

	} 

	for (int i = 1; i <= N; i++) { 

		vector<int> son;

		int x = p[i]; 

		vis[x] = 1, sum[x] = b[x]; 

		for (auto v : G[x]) {

			if (!vis[v] || getf(x) == getf(v)) continue; 

			son.push_back(getf(v)); 

			sum[x] += sum[getf(v)]; 

			pa[getf(v)] = x; 

		} 

		f[x] = sum[x] + a[x]; 

		for (auto v : son) f[x] = min(f[x], sum[x] - sum[v] + max(1ll * a[x], f[v])); 

	} 

	printf("%lld\n", f[p[N]]); 

    return 0; 

} 

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

using namespace std;



namespace TYC

{

	typedef long long ll;

	const int N = 1e5 + 5;



	int n, m, A[N], B[N], C[N], Fa[N], P[N], Vis[N];

	ll F[N], Sum[N];

	vector<int> E[N], T[N];



	bool cmp(const int a, const int b) { return C[a] < C[b]; }



	int find(const int a) { return a == Fa[a] ? a : Fa[a] = find(Fa[a]); }



	void dfs(const int u)

	{

		Sum[u] = B[u];

		for (int v : T[u])

		{

			dfs(v);

			Sum[u] += Sum[v];

		}

		if (!T[u].size())

			F[u] = C[u] + B[u];

		else 

		{

			F[u] = LLONG_MAX;

			for (int v : T[u])

				F[u] = min(F[u], max(F[v], (ll)C[u]) + Sum[u] - Sum[v]); 

		}

	}



	void work()

	{

		scanf("%d%d", &n, &m);

		for (int i = 1; i <= n; i++)

		{

			scanf("%d%d", &A[i], &B[i]);

			C[i] = max(A[i] - B[i], 0);

			P[i] = Fa[i] = i;

		}

		for (int i = 1, u, v; i <= m; i++)

		{

			scanf("%d%d", &u, &v);

			E[u].push_back(v);

			E[v].push_back(u);

		}

		sort(P + 1, P + 1 + n, cmp);

		for (int i = 1; i <= n; i++)

		{

			int u = P[i], f;

			Vis[u] = 1;

			for (int v : E[u])

				if (Vis[v] && (f = find(v))	!= u)

				{

					Fa[f] = u;

					T[u].push_back(f);

				}

		}

		dfs(P[n]);

		printf("%lld\n", F[P[n]]);

	}

}



int main()

{

	TYC::work();

	return 0;

}

// Optimized solution to the same problem (faster):
#include<iostream>

#include<algorithm> 

using namespace std;

struct node

{

	long long v,nxt;

};

node edge[200001];

struct reads

{

	long long num,data;

	bool operator < (const reads &a)const

	{

		return data<a.data;

	}

};

reads t[100001];

long long n,m,a[100001],b[100001],head[100001],len,rt[100001],sz[100001],Mx[100001];

int find(int x)

{

	if (rt[x]==x)

		return x;

	return rt[x]=find(rt[x]);

}

void unionn(int x,int y)

{

	sz[find(y)]+=sz[find(x)];

	Mx[find(y)]=min(Mx[find(y)],max(Mx[find(x)],a[find(y)]-b[find(y)]-sz[find(x)]));

	rt[find(x)]=find(y);

	return;

}

void add(int x,int y)

{

	edge[++len].v=y;

	edge[len].nxt=head[x];

	head[x]=len;

	return;

}

int main()

{

	int x,y;

	cin>>n>>m;

	for (int i=1;i<=n;++i)

	{

		cin>>a[i]>>b[i];

		rt[i]=i;

		sz[i]=b[i];

		t[i].num=i;

		Mx[i]=max(a[i]-b[i],0ll);

		t[i].data=Mx[i];

	}

	for (int i=1;i<=m;++i)

	{

		cin>>x>>y;

		add(x,y);

		add(y,x);

	}

	sort(t+1,t+n+1);

	for (int i=1;i<=n;++i)

		for (int j=head[t[i].num];j>0;j=edge[j].nxt)

			if (a[t[i].num]>=a[edge[j].v]&&find(edge[j].v)!=find(t[i].num))

				unionn(edge[j].v,t[i].num);

	cout<<Mx[find(1)]+sz[find(1)]<<endl;

	return 0;

}

// Fastest known solution for this problem:
// Original C++ solution (slower):
#include <bits/stdc++.h>

 

using namespace std;



int n, m, z[100005], par[100005], tb, tc;

long long x[100005], y[100005], sum[100005], dp[100005], ta;

vector< int > v[100005], vv[100005];



int find(int a) {

	return par[a] == a ? a : par[a] = find(par[a]);

}



int main() {

	scanf("%d%d", &n, &m);

	for (int i = 1; i <= n; i++) {

		scanf("%lld%lld", &ta, x + i);

		y[i] = max(ta - x[i], 0LL);

		z[i] = i;

	}

	sort(z + 1, z + n + 1, [](const int &a, const int &b) {return y[a] < y[b];});

	while (m--) {

		scanf("%d%d", &tb, &tc);

		v[tb].push_back(tc);

		v[tc].push_back(tb);

	}

	for (int i = 1; i <= n; i++) {

		tb = z[i];

		par[tb] = tb;

		sum[tb] = x[tb];

		dp[tb] = y[tb];

		for (int j: v[tb])

			if (par[j] && (j = find(j)) != tb) {

				vv[tb].push_back(j);

				par[j] = tb;

				sum[tb] += sum[j];

				dp[tb] = min(dp[tb], max(dp[j], y[tb]) - sum[j]);

			}

		dp[tb] += sum[tb];

	}

	printf("%lld\n", dp[z[n]]);

	return 0;

}


// Optimized solution to the same problem (faster):
#include <bits/stdc++.h>

 

using namespace std;



int n, m, z[100005], par[100005], tb, tc;

long long x[100005], y[100005], ta;

vector< int > v[100005];



int find(int a) {

	return par[a] == a ? a : par[a] = find(par[a]);

}



int main() {

	scanf("%d%d", &n, &m);

	for (int i = 1; i <= n; i++) {

		scanf("%lld%lld", &ta, x + i);

		y[i] = max(ta - x[i], 0LL);

		z[i] = i;

	}

	sort(z + 1, z + n + 1, [](const int &a, const int &b) {return y[a] < y[b];});

	while (m--) {

		scanf("%d%d", &tb, &tc);

		v[tb].push_back(tc);

		v[tc].push_back(tb);

	}

	for (int i = 1; i <= n; i++) {

		tb = z[i];

		par[tb] = tb;

		ta = y[tb];

		for (int j: v[tb])

			if (par[j] && (j = find(j)) != tb) {

				par[j] = tb;

				x[tb] += x[j];

				y[tb] = min(y[tb], max(y[j], ta) - x[j]);

			}

		y[tb] += x[tb];

	}

	printf("%lld\n", y[z[n]]);

	return 0;

}


// Fastest known solution for this problem:
// Original C++ solution (slower):
#include "stdio.h"

#include"queue"

#include "climits"

using namespace std;



queue<int>Q;



int island;

int query;

int kind;

int start;

int goal;

int connect[101][101] = {};

int price;

int dis[101] = {};



int main() {

	scanf("%d %d", &island, &query);

	while (island != 0) {

		for (int i = 0; i < 101; i++) {

			for (int j = 0; j < 101; j++) {

				connect[i][j] = INT_MAX;

			}

		}

		for (int i = 0; i < query; i++) {

			scanf("%d", &kind);

			if (kind == 1) {

				scanf("%d %d %d", &start, &goal, &price);

				if (connect[start][goal] > price) {

					connect[start][goal] = price;

					connect[goal][start] = price;

				}

			}

			else {

				scanf("%d %d", &start, &goal);

				Q.push(start);

				for (int i = 1; i < 101; i++) {

					dis[i] = INT_MAX;

				}

				dis[start] = 0;

				while (!Q.empty()) {

					for (int i = 1; i <= island; i++) {

						if (connect[Q.front()][i] != INT_MAX) {

							if (dis[i] > dis[Q.front()] + connect[Q.front()][i]) {

								dis[i] = dis[Q.front()] + connect[Q.front()][i];

								Q.push(i);

							}

						}

					}

					Q.pop();

				}

				if (dis[goal] == INT_MAX)printf("-1\n");

				else printf("%d\n", dis[goal]);

			}

		}

		scanf("%d %d", &island, &query);

	}

	return 0;

}

// Optimized solution to the same problem (faster):
#include "stdio.h"

#include "climits"



int n, m;

int edge[101][101];

int dis[101];

bool flag[101];

int box;

int s, e, p;



int main() {

	scanf("%d %d", &n, &m);

	while (n != 0) {

		for (int i = 1; i <= n; i++) {

			for (int j = 1; j <= n; j++) {

				edge[i][j] = 200000000;

			}

		}

		for (int i = 0; i < m; i++) {

			scanf("%d", &box);

			if (box == 1) {

				scanf("%d %d %d", &s, &e, &p);

				if (edge[s][e] > p) {

					edge[s][e] = p;

					edge[e][s] = p;

				}

			}

			else {

				scanf("%d %d", &s, &e);

				for (int j = 1; j <= n; j++) {

					flag[j] = true;

					dis[j] = 200000000;

				}

				dis[s] = 0;

				box = s;

				while (flag[e]) {

					flag[box] = false;

					for (int j = 1; j <= n; j++) {

						if (dis[box] + edge[box][j] < dis[j]) {

							dis[j] = dis[box] + edge[box][j];

						}

					}

					for (int j = 1; j <= n; j++) {

						if (flag[j]) {

							box = j;

							break;

						}

					}

					for (int j = box; j <= n; j++) {

						if (flag[j]) {

							if (dis[box] > dis[j])box = j;

						}

					}

				}

				if (dis[e] == 200000000)printf("-1\n");

				else printf("%d\n", dis[e]);

			}

		}

		scanf("%d %d", &n, &m);

	}

	return 0;

}

// Fastest known solution for this problem: