#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<vector<int>> adj_n(n);
  vector<int> from(n);
  auto rdfs = [&](auto self, int u)->pair<i64, i64> {
    i64 A = a[u], B = b[u];
    vector<pair<i64, i64>> d;
    for (auto i : adj_n[u]) {
      d.push_back(self(self, e[i].second));
    }
    sort(d.begin(), d.end(), [&](auto &x, auto &y) {
      if ((x.first < x.second) != (y.first < y.second)) {
        return x.first < x.second;
      }
      if (x.first < x.second) {
        return x.first < y.first;
      } else {
        return x.second > y.second;
      }
    });
    for (auto [x, y] : d) {
      if (B >= x) {
        // A - A + B - x + y
        B += -x + y;
      } else {
        // A - A + B < x 
        A = x - (-A + B);
        B = y;
      }
    }
    return {A, B};
  };
  for (int s = 0; s < (1 << cnt); ++s) {
    fill(from.begin(), from.end(), -1);
    for (int i = 0; i < n; ++i) {
      adj_n[i].clear();
    }
    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);
        }
      }
    }
    ans = min(ans, rdfs(rdfs, 0).first);
  }
  cout << ans << "\n";
}

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