[AtCoder ARC098] Donation| 建图 | 树型dp

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

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

44

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

582

int head[maxn];
int n,m,cnt,tot;
ll a[maxn],b[maxn],c[maxn],id[maxn];
int fa[maxn];
int lson[maxn],rson[maxn];
struct node{
  int v,nex;
}e[maxn];
void addEdge(int u,int v){
  e[cnt].v = v;
  e[cnt].nex = head[u];
  head[u] = cnt ++;
}
void init(){
  for(int i=0;i<maxn;i++) fa[i] = i,head[i] = -1;
  cnt = 0;
  tot = 0;
}
bool cmp(int x,int y){
  return a[x] < a[y];
}
int find(int x){
  if(x == fa[x]) return x;
  else return fa[x] = find(fa[x]);
}
void add(int u,int v){
  int fau = find(u);
  int fav = find(v);
  if(fau == fav) return ;
  tot ++;
  u = fau;
  v = fav;
  lson[tot] = u;
  rson[tot] = v;
  a[tot] = max(a[u],a[v]);
  b[tot] = b[u] + b[v];///cost cal
  fa[u] = tot;
  fa[v] = tot;
  fa[tot] = tot;
}
ll dp[maxn];
void dfs(int u){
  if(lson[u]){
    dfs(lson[u]);
    dfs(rson[u]);
  }else dp[u] = a[u];
  dp[u] = min(
  max(a[u]-b[lson[u]],dp[lson[u]]),
  max(a[u]-b[rson[u]],dp[rson[u]])
  );
}
int main()
{
  init();
  n = read,m = read;
  for(int i=1;i<=n;i++) a[i] = read,b[i] = read;
  for(int i=1;i<=n;i++) a[i] = max(a[i] - b[i], 0LL),id[i] = i;
  sort(id+1,id+1+n,cmp);
  for(int i=1;i<=m;i++){
    int u = read,v = read;
    addEdge(u,v);
    addEdge(v,u);
  }
  /*for(int i=1;i<=n;i++){
    cout<<id[i]<<' ';
  }
  puts("");*/
  tot = n;
  // puts("ok");
  for(int i=1;i<=n;i++){
    int u = id[i];
    for(int j = head[u]; ~j; j = e[j].nex){
      int to = e[j].v;
      if(a[to] <= a[u]) add(u,to);
    }
  }
  dfs(tot);
  cout << dp[tot] + b[tot] <<endl;
    return 0;
}