func_code_string: #include <bits/stdc++.h>   using ll = long long;   const ll LINF = 1e13;   using namespace std;   namespace ProconLib {   template <typename cost_t = long long, bool hasNegativeCost = false,             cost_t INF = LINF>   class Flow {    public:     struct Edge {       int to;       cost_t cap, rev;       cost_t cost;     };     using Edges = vector<Edge>;     using Graph = vector<Edges>;       private:     int N;     Graph g;     vector<int> level;     vector<int> iter;     void bfs(int s);     cost_t dfs(int v, int t, cost_t f);       public:     Flow(int N) : N(N), g(N){};     void addEdge(int from, int to, cost_t cap);     void addEdge(int from, int to, cost_t cap, cost_t cost);     cost_t maxFlow(int s, int t);     cost_t minCostFlow(int s, int t, cost_t f);   };   template <typename cost_t, bool hasNegativeCost, cost_t INF>   void Flow<cost_t, hasNegativeCost, INF>::addEdge(int from, int to, cost_t cap) {     g[from].push_back({to, cap, int(g[to].size()), 0});     g[to].push_back({from, cost_t(0), int(g[from].size()) - 1, 0});   }   template <typename cost_t, bool hasNegativeCost, cost_t INF>   void Flow<cost_t, hasNegativeCost, INF>::addEdge(int from, int to, cost_t cap,                                                    cost_t cost) {     g[from].push_back({to, cap, int(g[to].size()), cost});     g[to].push_back({from, cost_t(0), int(g[from].size()) - 1, -cost});   }   template <typename cost_t, bool hasNegativeCost, cost_t INF>   cost_t Flow<cost_t, hasNegativeCost, INF>::maxFlow(int s, int t) {     cost_t flow = 0;     while (true) {       bfs(s);       if (level[t] < 0) return flow;       iter.assign(N, 0);       cost_t f;       while ((f = dfs(s, t, INF)) > 0) {         flow += f;       }     }   }   template <typename cost_t, bool hasNegativeCost, cost_t INF>   void Flow<cost_t, hasNegativeCost, INF>::bfs(int s) {     level.assign(N, -1);     queue<int> que;     level[s] = 0;     que.push(s);     while (!que.empty()) {       int v = que.front();       que.pop();       for (int i = 0; i < g[v].size(); i++) {         Edge& e = g[v][i];         if (e.cap > 0 && level[e.to] < 0) {           level[e.to] = level[v] + 1;           que.push(e.to);         }       }     }   }   template <typename cost_t, bool hasNegativeCost, cost_t INF>   cost_t Flow<cost_t, hasNegativeCost, INF>::dfs(int v, int t, cost_t f) {     if (v == t) return f;     for (int& i = iter[v]; i < g[v].size(); i++) {       Edge& e = g[v][i];       if (e.cap > 0 && level[v] < level[e.to]) {         cost_t d = dfs(e.to, t, min(f, e.cap));         if (d > 0) {           e.cap -= d;           g[e.to][e.rev].cap += d;           return d;         }       }     }     return 0;   }   template <typename cost_t, bool hasNegativeCost, cost_t INF>   cost_t Flow<cost_t, hasNegativeCost, INF>::minCostFlow(int s, int t, cost_t f) {     using P = pair<cost_t, int>;     cost_t res = 0;     vector<cost_t> h(N, 0);     vector<int> used(N), preve(N), prevv(N);     vector<cost_t> dist(N);     while (f > 0) {       fill(dist.begin(), dist.end(), INF);       dist[s] = 0;       if (!hasNegativeCost) {         fill(used.begin(), used.end(), 0);         priority_queue<P, vector<P>, greater<P>> que;         que.push(make_pair(cost_t(0), s));         while (!que.empty()) {           P p = que.top();           que.pop();           int v = p.second;           if (used[v]) continue;           used[v] = true;           for (int i = 0; i < g[v].size(); i++) {             Edge& e = g[v][i];             if (e.cap > 0 && dist[e.to] > dist[v] + e.cost + h[v] - h[e.to]) {               dist[e.to] = dist[v] + e.cost + h[v] - h[e.to];               prevv[e.to] = v;               preve[e.to] = i;               que.push(make_pair(dist[e.to], e.to));             }           }         }       } else {         bool update = true;         while (update) {           update = false;           for (int v = 0; v < N; v++) {             if (dist[v] == INF) continue;             for (int i = 0; i < g[v].size(); i++) {               Edge& e = g[v][i];               if (e.cap > 0 && dist[e.to] > dist[v] + e.cost) {                 dist[e.to] = dist[v] + e.cost;                 prevv[e.to] = v;                 preve[e.to] = i;                 update = true;               }             }           }         }       }       if (dist[t] == INF) {         return -1;       }       if (!hasNegativeCost) {         for (int v = 0; v < N; v++) h[v] += dist[v];       }       cost_t d = f;       for (int v = t; v != s; v = prevv[v]) {         d = min(d, g[prevv[v]][preve[v]].cap);       }       f -= d;       if (!hasNegativeCost) {         res += d * h[t];       } else {         res += d * dist[t];       }       for (int v = t; v != s; v = prevv[v]) {         Edge& e = g[prevv[v]][preve[v]];         e.cap -= d;         g[v][e.rev].cap += d;       }     }     return res;   }   }  // namespace ProconLib   struct Spaceship {     int x, a, f, p;   };   struct Base {     int x, d, g;   };   using namespace ProconLib;   using vvi = vector<vector<int>>;   void dfs(int v, vvi& g, vector<int>& used, vector<int>& vs) {     used[v] = true;     vs.push_back(v);     for (auto to : g[v]) {       if (used[to]) continue;       dfs(to, g, used, vs);     }   }   int main() {     int n, m;     cin >> n >> m;     vector<vector<int>> dist(n, vector<int>(n, 1e9 + 5));     for (int i = 0; i < m; i++) {       int u, v;       cin >> u >> v;       u--, v--;       dist[u][v] = 1;       dist[v][u] = 1;     }     for (int i = 0; i < n; i++) dist[i][i] = 0;     int s, b, k;     cin >> s >> b >> k;     vector<Spaceship> ship(s);     for (int i = 0; i < s; i++) {       cin >> ship[i].x >> ship[i].a >> ship[i].f >> ship[i].p, ship[i].x--;     }     vector<Base> base(b);     for (int i = 0; i < b; i++) {       cin >> base[i].x >> base[i].d >> base[i].g;       base[i].x--;     }     vvi sg(s);     for (int i = 0; i < k; i++) {       int s1, s2;       cin >> s1 >> s2;       s1--, s2--;       sg[s1].push_back(s2);     }     for (int k = 0; k < n; k++) {       for (int i = 0; i < n; i++) {         for (int j = 0; j < n; j++) {           dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);         }       }     }     vector<ll> profit(s, -LINF);     vector<vector<int>> bids(n);     for (int i = 0; i < b; i++) {       bids[base[i].x].push_back(i);     }     auto cmp = [&](int lhs, int rhs) { return base[lhs].d < base[rhs].d; };     for (int i = 0; i < n; i++) sort(bids[i].begin(), bids[i].end(), cmp);     vector<vector<int>> accMax(n);     for (int i = 0; i < n; i++) {       accMax[i].resize(bids[i].size() + 1);       for (int j = 0; j < bids[i].size(); j++) {         accMax[i][j + 1] = max(accMax[i][j], base[bids[i][j]].g);       }     }     for (int i = 0; i < s; i++) {       int x = ship[i].x;       for (int v = 0; v < n; v++) {         if (dist[x][v] <= ship[i].f) {           int lb = -1, ub = bids[v].size();           while (ub - lb > 1) {             int mid = (lb + ub) / 2;             if (base[bids[v][mid]].d <= ship[i].a)               lb = mid;             else               ub = mid;           }           ll sc = accMax[v][ub] - ship[i].p;           if (ub > 0) profit[i] = max(profit[i], sc);         }       }     }     auto doFlow = [&](const vvi& graph, const vector<ll>& mpPro) {       int n = graph.size();       const int S = n;       const int T = n + 1;       Flow<ll> flow(n + 2);       ll sum = 0;       for (int i = 0; i < n; i++) {         if (mpPro[i] > 0) {           sum += mpPro[i];           flow.addEdge(S, i, mpPro[i]);           flow.addEdge(i, T, 0);         } else {           flow.addEdge(S, i, 0);           flow.addEdge(i, T, -mpPro[i]);         }       }       for (int i = 0; i < n; i++) {         for (auto to : graph[i]) {           flow.addEdge(i, to, LINF);         }       }       return sum - flow.maxFlow(S, T);     };     vvi undirSG(s);     for (int i = 0; i < s; i++) {       for (auto to : sg[i]) {         undirSG[i].push_back(to);         undirSG[to].push_back(i);       }     }     ll res = 0;     vector<int> used(s);     for (int i = 0; i < s; i++) {       if (!used[i]) {         vector<int> vs;         dfs(i, undirSG, used, vs);         if (vs.size() == 1) {           if (profit[i] > 0) res += profit[i];           continue;         }         map<int, int> mp;         int id = 0;         for (auto v : vs) {           mp[v] = id++;         }         vvi mapG(id);         vector<ll> mpPro(id);         for (auto v : vs) {           mpPro[mp[v]] = profit[v];           for (auto to : sg[v]) {             mapG[mp[v]].push_back(mp[to]);           }         }         res += doFlow(mapG, mpPro);       }     }     cout << res << endl;     return 0;   }   