#include <bits/stdc++.h>
#define F(i, a, b) for (int i = (a); i <= (b); ++i)
#define dF(i, a, b) for (int i = (a); i >= (b); --i)

using namespace std;
typedef long long LL;
typedef unsigned long long ull;
typedef unsigned int uint;
typedef pair<int, int> pii;
const int P = 900001;
const int M = 2e7 + 5;
const LL inf = 1e18;

int n, m; LL a[40], b[40], out[40];

int nxtt[M]; LL idd[M], vall[M], bit[40];
struct Hash {
  int tot, head[P], *nxt; LL *id, *val;
  void Insert(LL x) {
    int u = x % P;
    for (int i = head[u]; i; i = nxt[i])
      if (id[i] == x) return ;
    id[++tot] = x, val[tot] = inf;
    nxt[tot] = head[u], head[u] = tot;
  }
  LL Query(LL x) {
    for (int i = head[x % P]; i; i = nxt[i])
      if (id[i] == x) return val[i];
  }
} f[36];

int main() {
  // freopen("clear.in", "r", stdin);
  // freopen("clear.out", "w", stdout);
  ios::sync_with_stdio(0);
  cin.tie(0), cout.tie(0);
  cin >> n >> m;
  F(i, 1, n) bit[i] = 1ll << i - 1;
  F(i, 2, n) cin >> a[i] >> b[i];
  F(i, 1, m) { int u, v; cin >> u >> v, out[u] |= bit[v]; }
  f[n - 1].nxt = nxtt, f[n - 1].id = idd, f[n - 1].val = vall;
  f[n - 1].Insert((1ll << n) - 2);
  dF(i, n - 2, 0) {
    f[i].nxt = f[i + 1].nxt + f[i + 1].tot + 1;
    f[i].id = f[i + 1].id + f[i + 1].tot + 1;
    f[i].val = f[i + 1].val + f[i + 1].tot + 1;
    F(j, 1, f[i + 1].tot) {
      LL st = f[i + 1].id[j], nxt = 0;
      F(k, 1, n) if (!(st & bit[k])) nxt |= out[k];
      F(k, 1, n) if ((nxt & bit[k]) && (st & bit[k]))
        f[i].Insert(st ^ bit[k]);
    }
  }
  f[0].val[1] = 0;
  F(i, 0, n - 2) {
    F(j, 1, f[i + 1].tot) {
      LL st = f[i + 1].id[j], nxt = 0;
      F(k, 1, n) if (!(st & bit[k])) nxt |= out[k];
      F(k, 1, n) if ((nxt & bit[k]) && (st & bit[k])) {
        LL dp = f[i].Query(st ^ bit[k]);
        f[i + 1].val[j] = min(f[i + 1].val[j], a[k] + max(dp - b[k], 0ll));
      }
    }
  }
  cout << f[n - 1].val[1] << "\n";
  return 0;
}