也是道不错的题，大概是第一次做到按点权建 Kruskal 重构树。

捐赠的过程是一个经典的问题，一般的做法是倒着考虑后贪心。倒着考虑这个问题，于是变成了选择一个初始点，在任意点的时候身上的钱的数量必须不小于 $\max(A_i - B_i , 0)$ ，并且到达一个点后就可以选择获得 $B_i$ 块钱，你需要最小化最终的钱数。

为了方便，我们设 $C_i = \max(A_i - B_i , 0)$ 。如果是个完全图就可以直接按照 $C_i$ 从小到大贪心拿。但是事实上，由于具有图的限制，想要拿某个很小的 $C_i$ 需要经过一些很大的 $C_i$ 。因此可以按照点权建立出 kruskal 重构树，具体来说，令一个点的子树为这个点可以通过走小于等于这个点点权的点走到的连通块，建立的方法类似于用边建重构树，按照点权从小到大排序，然后枚举出边，找到所有相连的权值小于这个点的点，然后连向它所在连通块最靠上的点。

然后考虑在这个树上做 $dp$ ，设 $dp[u]$ 为最开始初始点选在 $u$ ，走完整个 $u$ 这个子树得到的最小钱数。于是转移就是枚举一个子树 $v$ 为初始点选择的子树，设 $S[u]$ 为 $u$ 子树内所有 $B$ 的和，于是有

$$dp[u] = \min_{v} \{ S[u] - S[v] + \max\{ C[u] , dp[v] \}\}$$

因为从 $v$ 子树出来的时候，必须得满足 $C[u]$ 这个限制，而且只要满足 $C[u]$ 就一定可以满足子树内其他所有点的限制，因此直接加上剩下的子树可以获得的钱数 $S[u] - S[v]$ 。

复杂度 $O(n\log n)$ 。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "queue"
using namespace std;
#define MAXN 200006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
typedef long long ll;
int n , m;
int A[MAXN] , B[MAXN] , C[MAXN];

struct ed {
	int u , v , w;
} E[MAXN] ;

int fa[MAXN];
int find( int x ) {
	return fa[x] == x ? x : fa[x] = find( fa[x] );
}

vi G[MAXN];
ll dp[MAXN] , S[MAXN];
void dfs( int u ) {
	S[u] = B[u] , dp[u] = 0x3f3f3f3f3f3f3f3f;
	if( !G[u].size() ) {
		dp[u] = B[u] + C[u];
		return;
	}
	for( int v : G[u] ) 
		dfs( v ) , S[u] += S[v];
	for( int v : G[u] ) 
		dp[u] = min( dp[u] , S[u] - S[v] + max( 1ll * C[u] , dp[v] ) );
}

vi g[MAXN];
int idx[MAXN];
int fk[MAXN];

void solve() {
	cin >> n >> m;
	rep( i , 1 , n ) scanf("%d%d",A + i,B + i) , C[i] = max( A[i] - B[i] , 0 );
	rep( i , 1 , m ) {
		int u , v;
		scanf("%d%d",&u,&v);
		g[u].pb( v ) , g[v].pb( u );
	}
	rep( i , 1 , n ) idx[i] = fa[i] = i;
	sort( idx + 1 , idx + 1 + n , [&]( int a , int b ) { return C[a] < C[b]; } );
	rep( i , 1 , n ) {
		int u = idx[i];
		for( int v : g[u] ) if( fk[v] ) {
			int t = find( v );
			if( t == u ) continue;
			G[u].pb( t );
			fa[t] = u;
		}
		fk[u] = 1;
	}
	dfs( idx[n] );
	cout << dp[idx[n]] << endl;
}

signed main() {
//    int T;cin >> T;while( T-- ) solve();
    solve();
}