#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();
  vector<int> o(n);
  iota(o.begin(), o.end(), 0);
  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];
    }
  });
  i64 ans = 1E18;
  vector<vector<int>> adj_n(n);
  vector<int> from(n);
  auto rdfs = [&](auto self, int u, i64 &A, i64 &B)->void {
    if (B >= a[u]) {
      B += -a[u] + b[u];
    } else {
      A = a[u] - (-A + B);
      B = b[u];
    }
    for (auto i : adj_n[u]) {
      int v = e[i].second;
      self(self, v, A, B);
    }
  };
  for (int s = 0; s < (1 << cnt); ++s) {
    fill(from.begin(), from.end(), -1);
    for (int i = 0; i < n; ++i) {
      vector<int>().swap(adj_n[i]);
    }
    for (int i = 0; i < cnt; ++i) {
      if (s >> i & 1) {
        used[c[i]] = 2;
        auto [u, v] = e[c[i]];
        if (from[v] == -1) {
          from[v] = u;
          adj_n[u].push_back(c[i]);
        }
      }
    }
    for (int i = 0; i < m; ++i) {
      if (used[i] == 1) {
        auto [u, v] = e[i];
        if (from[v] == -1) {
          from[v] = u;
          adj_n[u].push_back(i);
        }
      }
    }
    for (int i : o) {
      if (i) {
        adj_n[from[i]].push_back(i);
      }
    }
    i64 A = 0, B = 0;
    rdfs(rdfs, 0, A, B);
    ans = min(ans, A);
  }
  cout << ans << "\n";
}

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