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
using namespace std;
const int N = 1e5 + 10;
struct data {
  int nt, to;
} a[N << 1];
ll A[N], B[N], dp[N], s[N];
int p[N], f[N], vs[N];
int head[N], cnt = 0;

void add(int x, int y) {
  a[++cnt].to = y;
  a[cnt].nt = head[x];
  head[x] = cnt;
}

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

int find(int k) {
  return f[k] == k ? f[k] : f[k] = find(f[k]);
}

int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for(int i = 1; i <= n; ++i) {
    p[i] = f[i] = i;
    scanf("%lld%lld", &A[i], &B[i]);
    s[i] = B[i];
    dp[i] = A[i] = max(A[i] - B[i], 0ll);
  }
  sort(p + 1, p + 1 + n, cmp);
  for(int i = 1, x, y; i <= m; ++i) {
    scanf("%d%d", &x, &y);
    add(x, y), add(y, x);
  }
  for(int o = 1; o <= n; ++o) {
    int u = p[o];
    vs[u] = 1;
    for(int i = head[u]; i; i = a[i].nt) {
      int to = a[i].to;
      if(vs[to]) {
        int fx = find(u), fy = find(to);
        if(fx == fy) continue;
        f[fy] = fx, s[fx] += s[fy];
        dp[fx] = min(dp[fx], max(dp[fy], A[fx] - s[fy]));
      }
    }
  }
  printf("%lld\n", dp[find(1)] + s[find(1)]);
  return 0;
}