#include <bits/stdc++.h>
using namespace std;

#define debug(...) fprintf(stderr, __VA_ARGS__)

using i64 = long long;

int n, m;

void solve1() {
  vector<i64> a(n), b(n);
  for (int i = 1; i < n; ++i) {
    cin >> a[i] >> b[i];
  }
  vector<int> from(1 << n);
  for (int i = 0; i < m; ++i) {
    int u, v;
    cin >> u >> v, u--, v--;
    from[v] |= 1 << u;
  }
  vector<i64> w(1 << n);
  for (int s = 0; s < (1 << n); ++s) if (s & 1) {
    for (int i = 0; i < n; ++i) {
      if (s >> i & 1) {
        w[s] += -a[i] + b[i];
      }
    }
  }
  vector<i64> f(1 << n, 1E18);
  f[1] = 0;
  for (int s = 2; s < (1 << n); ++s) if (s & 1) {
    for (int i = 1; i < n; ++i) {
      if (s >> i & 1 && from[i] & s) {
        int t = s ^ (1 << i);
        /*
          f[t] + w[t] >= a[i] -> f[t] + w[t]
          f[t] + w[t] < a[i]  -> a[i] - w[t]
        */
        if (f[t] + w[t] >= a[i]) f[s] = min(f[s], f[t]);
        else f[s] = min(f[s], a[i] - w[t]);
      }
    }
  }
  cout << f[(1 << n) - 1] << "\n";
}

void solve2() {
  vector<i64> a(n), b(n);
  for (int i = 1; i < n; ++i) {
    cin >> a[i] >> b[i];
  }
  vector<pair<int, int>> e(m);
  vector<vector<int>> adj(n);
  for (int i = 0; i < m; ++i) {
    auto &[u, v] = e[i];
    cin >> u >> v, u--, v--;
    adj[u].push_back(i);
  }
  vector<int> used(m), vis(n);
  auto dfs = [&](auto self, int u)->void {
    vis[u] = 1;
    for (auto i : adj[u]) {
      int v = e[i].second;
      if (!vis[v]) {
        self(self, v);
        used[i] = 1;
      }
    }
  };
  dfs(dfs, 0);
  vector<int> c;
  for (int i = 0; i < m; ++i) {
    if (!used[i]) {
      c.push_back(i);
    }
  }
  int cnt = c.size();
  i64 ans = 1E18;
  vector<int> from(n);
  vector<i64> A(n), B(n);
  auto rdfs = [&](auto self)->void {
    vector<int> o;
    for (int i = 1; i < n; ++i) {
      if (from[i] != -1) {
        o.push_back(i);
      }
    }
    if (!o.size()) {
      ans = min(ans, A[0]);
      return;
    }
    sort(o.begin(), o.end(), [&](auto u, auto v) {
      if ((A[u] < B[u]) != (A[v] < B[v])) {
        return A[u] < B[u];
      }
      if (A[u] < B[u]) {
        return A[u] < A[v];
      } else {
        return B[u] > B[v];
      }
    });
    int cur = o[0], tar = from[cur];
    from[cur] = -1;
    if (B[tar] >= A[cur]) {
      B[tar] += -A[cur] + B[cur];
    } else {
      A[tar] = A[cur] - (-A[tar] + B[tar]);
      B[tar] = B[cur];
    }
    for (int i = 1; i < n; ++i) {
      if (from[i] == cur) {
        from[i] = tar;
      }
    }
    self(self);
  };
  for (int s = 0; s < (1 << cnt); ++s) {
    fill(from.begin(), from.end(), -1);
    for (int i = 0; i < cnt; ++i) {
      if (s >> i & 1) {
        auto [u, v] = e[c[i]];
        if (from[v] == -1) {
          from[v] = u;
        }
      }
    }
    for (int i = 0; i < m; ++i) {
      if (used[i] == 1) {
        auto [u, v] = e[i];
        if (from[v] == -1) {
          from[v] = u;
        }
      }
    }
    copy(a.begin(), a.end(), A.begin());
    copy(b.begin(), b.end(), B.begin());
    rdfs(rdfs);
  }
  cout << ans << "\n";
}

int main() {
  cin.tie(0)->sync_with_stdio(0);
  cin >> n >> m;
  if (n <= 26) {
    solve1();
  } else {
    solve2();
  }
  return 0;
}