The rebels have saved enough gold to launch a full-scale attack. Now the situation is flipped, the rebels will send out the spaceships to attack the Empire bases!

The galaxy can be represented as an undirected graph with n planets (nodes) and m wormholes (edges), each connecting two planets.

A total of s rebel spaceships and b empire bases are located at different planets in the galaxy.

Each spaceship is given a location x, denoting the index of the planet on which it is located, an attacking strength a, a certain amount of fuel f, and a price to operate p.

Each base is given a location x, a defensive strength d, and a certain amount of gold g.

A spaceship can attack a base if both of these conditions hold: 

  * the spaceship's attacking strength is greater or equal than the defensive strength of the base 
  * the spaceship's fuel is greater or equal to the shortest distance, computed as the number of wormholes, between the spaceship's node and the base's node 



The rebels are very proud fighters. So, if a spaceship cannot attack any base, no rebel pilot will accept to operate it.

If a spaceship is operated, the profit generated by that spaceship is equal to the gold of the base it attacks minus the price to operate the spaceship. Note that this might be negative. A spaceship that is operated will attack the base that maximizes its profit.

Darth Vader likes to appear rich at all times. Therefore, whenever a base is attacked and its gold stolen, he makes sure to immediately refill that base with gold.

Therefore, for the purposes of the rebels, multiple spaceships can attack the same base, in which case each spaceship will still receive all the gold of that base.

The rebels have tasked Heidi and the Doctor to decide which set of spaceships to operate in order to maximize the total profit.

However, as the war has been going on for a long time, the pilots have formed unbreakable bonds, and some of them refuse to operate spaceships if their friends are not also operating spaceships.

They have a list of k dependencies of the form s_1, s_2, denoting that spaceship s_1 can be operated only if spaceship s_2 is also operated.

Input

The first line of input contains integers n and m (1 ≤ n ≤ 100, 0 ≤ m ≤ 10000), the number of nodes and the number of edges, respectively.

The next m lines contain integers u and v (1 ≤ u, v ≤ n) denoting an undirected edge between the two nodes.

The next line contains integers s, b and k (1 ≤ s, b ≤ 10^5, 0 ≤ k ≤ 1000), the number of spaceships, bases, and dependencies, respectively.

The next s lines contain integers x, a, f, p (1 ≤ x ≤ n, 0 ≤ a, f, p ≤ 10^9), denoting the location, attack, fuel, and price of the spaceship. Ships are numbered from 1 to s.

The next b lines contain integers x, d, g (1 ≤ x ≤ n, 0 ≤ d, g ≤ 10^9), denoting the location, defence, and gold of the base.

The next k lines contain integers s_1 and s_2 (1 ≤ s_1, s_2 ≤ s), denoting a dependency of s_1 on s_2.

Output

Print a single integer, the maximum total profit that can be achieved.

Example

Input


6 7
1 2
2 3
3 4
4 6
6 5
4 4
3 6
4 2 2
1 10 2 5
3 8 2 7
5 1 0 2
6 5 4 1
3 7 6
5 2 3
4 2
3 2


Output


2

Note

The optimal strategy is to operate spaceships 1, 2, and 4, which will attack bases 1, 1, and 2, respectively.
#include <bits/stdc++.h>
using namespace std;
using pii = pair<int, int>;
using vpii = vector<pii>;
using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;
using vll = vector<long long>;
template <class T>
using min_queue = priority_queue<T, vector<T>, greater<T>>;
template <class T>
istream &operator>>(istream &, vector<T> &);
template <class T>
ostream &operator<<(ostream &, const vector<T> &);
template <class T, class U>
istream &operator>>(istream &, pair<T, U> &);
template <class T, class U>
ostream &operator<<(ostream &, const pair<T, U> &);
template <class T>
struct Inf {
  static constexpr T inf() {
    return std::numeric_limits<T>::has_infinity()
               ? std::numeric_limits<T>::infinty()
               : std::numeric_limits<T>::max();
  }
};
template <>
struct Inf<int> {
  static constexpr int inf() { return 0x3f3f3f3f; }
};
template <>
struct Inf<long long> {
  static constexpr long long inf() { return 0x3f3f3f3f3f3f3f3fLL; }
};
constexpr int INF = Inf<int>::inf();
constexpr ll BINF = Inf<ll>::inf();
template <class T>
class Dinic {
 private:
  struct edge {
    int from, to;
    T cap;
    edge *rev;
    edge(int u, int v, T c) : from(u), to(v), cap(c), rev(nullptr) {}
  };
  static constexpr T INF = Inf<T>::inf();
  int n, s, t;
  std::vector<std::vector<edge *>> g;

 public:
  Dinic(int n, int s, int t) : n(n), s(s), t(t), g(n) {}
  ~Dinic() {
    for (auto v : g)
      for (edge *e : v) delete e;
  }
  void addEdge(int u, int v, T c) {
    edge *in = new edge(u, v, c);
    edge *out = new edge(v, u, 0);
    g[u].push_back(in);
    g[v].push_back(out);
    in->rev = out;
    out->rev = in;
  }
  T maxFlow() {
    T mxf = 0;
    std::vector<T> dist(n, INF), vis(n);
    std::function<T(int, T)> dfs = [&](int u, T fo) -> T {
      if (u == t) return fo;
      for (; vis[u] < int(g[u].size()); vis[u]++) {
        edge *e = g[u][vis[u]];
        int v = e->to;
        if (dist[v] != dist[u] + 1 || e->cap <= 0) continue;
        T foo = dfs(v, std::min(fo, e->cap));
        if (foo > 0) {
          e->cap -= foo;
          e->rev->cap += foo;
          return foo;
        }
      }
      return 0;
    };
    for (;;) {
      for (int i = 0; i < n; i++) dist[i] = INF, vis[i] = 0;
      std::queue<int> q;
      q.push(s);
      dist[s] = 0;
      while (!q.empty()) {
        int u = q.front();
        q.pop();
        if (u == t) break;
        for (edge *e : g[u]) {
          int v = e->to;
          if (e->cap > 0 && dist[v] == INF) {
            dist[v] = dist[u] + 1;
            q.push(v);
          }
        }
      }
      if (dist[t] == INF) break;
      while (T fo = dfs(s, INF)) mxf += fo;
    }
    return mxf;
  }
};
template <class T>
constexpr T Dinic<T>::INF;
int solve() {
  int n, m;
  cin >> n >> m;
  vvi dp(n, vi(n, INF));
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    dp[u][v] = dp[v][u] = 1;
  }
  for (int i = 0; i < n; i++) dp[i][i] = 0;
  for (int k = 0; k < n; k++)
    for (int i = 0; i < n; i++)
      for (int j = 0; j < n; j++) dp[i][j] = min(dp[i][j], dp[i][k] + dp[k][j]);
  int s, b, k;
  cin >> s >> b >> k;
  vi xs(s), as(s), fs(s), ps(s), xb(b), db(b), gb(b);
  for (int i = 0; i < s; i++) {
    cin >> xs[i] >> as[i] >> fs[i] >> ps[i];
    xs[i]--;
  }
  for (int i = 0; i < b; i++) {
    cin >> xb[i] >> db[i] >> gb[i];
    xb[i]--;
  }
  vll canGet(s, -BINF);
  vector<vpii> bsList(n);
  for (int i = 0; i < b; i++) bsList[xb[i]].emplace_back(db[i], gb[i]);
  for (int i = 0; i < n; i++) {
    sort(bsList[i].begin(), bsList[i].end());
    int z = bsList[i].size();
    for (int j = 1; j < z; j++)
      bsList[i][j].second = max(bsList[i][j].second, bsList[i][j - 1].second);
  }
  for (int i = 0; i < s; i++)
    for (int j = 0; j < n; j++) {
      if (dp[xs[i]][j] > fs[i]) continue;
      auto it =
          upper_bound(bsList[j].begin(), bsList[j].end(), pii{as[i], INF});
      if (it == bsList[j].begin()) continue;
      it--;
      canGet[i] = max(canGet[i], ll(it->second));
    }
  for (int i = 0; i < s; i++) canGet[i] -= ps[i];
  ll ans = 0;
  Dinic<ll> g(s + 2, s, s + 1);
  for (int i = 0; i < s; i++) {
    if (canGet[i] >= 0) {
      ans += canGet[i];
      g.addEdge(s, i, canGet[i]);
    } else {
      g.addEdge(i, s + 1, -canGet[i]);
    }
  }
  for (int i = 0; i < k; i++) {
    int u, v;
    cin >> u >> v;
    u--, v--;
    g.addEdge(u, v, BINF);
  }
  ans -= g.maxFlow();
  cout << ans << endl;
  return 0;
}
int main() {
  ios::sync_with_stdio(0);
  solve();
  return 0;
}
template <class T>
istream &operator>>(istream &is, vector<T> &v) {
  for (auto it = v.begin(); it != v.end(); ++it) is >> *it;
  return is;
}
template <class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  for (auto it = v.begin(); it != v.end();)
    os << *it, os << " \n"[++it == v.end()];
  return os;
}
template <class T, class U>
istream &operator>>(istream &is, pair<T, U> &p) {
  return is >> p.first >> p.second;
}
template <class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  return os << p.first << ' ' << p.second;
}
