tobruk

#include <fstream>
#include <algorithm>
#include <vector>
#include <queue>
#include <utility>
#include <limits>
#include <cctype>

using namespace std;


ifstream fin ("tobruk.in");
ofstream fout ("tobruk.out");

struct base_t {
    int_fast64_t position, defense, oil;
    friend ifstream& operator >> (ifstream& flux, base_t& b) {
        flux >> b.position >> b.defense >> b.oil;
        return flux;
    }
    bool operator < (const base_t& b) const {
        return this->defense < b.defense;
    }
};

struct squad_t {
    int_fast64_t position, strength, fuel, price;
    friend ifstream& operator >> (ifstream& flux, squad_t& s) {
        flux >> s.position >> s.strength >> s.fuel >> s.price;
        return flux;
    }
};

class Dinic;
class Flow_Edge {
private:
    int from, to;
    int_fast64_t capacity, flow = 0LL;
public:
    Flow_Edge (const int& from, const int& to, const int_fast64_t& capacity): from (from), to (to), capacity (capacity) {
    }
    friend Dinic;
};

constexpr auto Inf = numeric_limits <int_fast64_t>::max () >> 1LL;
using Ip = pair <int_fast64_t, int_fast64_t>;
using Vi = vector <int>;
using VVi = vector <Vi>;
using Vi64 = vector <int_fast64_t>;
using VVi64 = vector <Vi64>;
using VIp = vector <Ip>;
using VVIp = vector <VIp>;
using Vf = vector <Flow_Edge>;
using Vs = vector <squad_t>;
using Vb = vector <base_t>;
using Qi = queue <int>;

class Dinic {
private:
    Vf Edges;
    VVi Adj;
    int n, s, t;
    Vi Level, Ptr;
    Qi Q;
    bool bfs () {
        while (!Q.empty ()) {
            int v = Q.front (); Q.pop ();
            for (const auto& id: Adj[v]) {
                if (Edges[id].capacity - Edges[id].flow < 1)
                    continue;
                if (Level[Edges[id].to] != -1)
                    continue;
                Level[Edges[id].to] = Level[v] + 1;
                Q.push (Edges[id].to);
            }
        }
        return Level[t] != -1;
    }
    int_fast64_t dfs (const int& v, const int_fast64_t& pushed) {
        if (!pushed)
            return 0LL;
        if (v == t)
            return pushed;
        for (int& cid = Ptr[v]; cid < (int)Adj[v].size (); ++ cid) {
            int id = Adj[v][cid], u = Edges[id].to;
            if (Level[v] + 1 != Level[u] || Edges[id].capacity - Edges[id].flow < 1)
                continue;
            int_fast64_t transport = dfs (u, min (pushed, Edges[id].capacity - Edges[id].flow));
            if (!transport)
                continue;
            Edges[id].flow += transport;
            Edges[id ^ 1].flow -= transport;
            return transport;
        }
        return 0LL;
    }
public:
    Dinic (const int& n, const int& s, const int& t): n (n), s (s), t (t) {
        Adj.resize (n), Level.resize (n), Ptr.resize (n);
    }
    void add_edge (const int& u, const int& v, const int_fast64_t& cap) {
        if (u == v) return;
        Edges.emplace_back (u, v, cap);
        Adj[u].emplace_back (Edges.size () - 1);
        Edges.emplace_back (v, u, 0);
        Adj[v].emplace_back (Edges.size () - 1);
    }
    int_fast64_t max_flow () {
        int_fast64_t f = 0LL;
        while (true) {
            fill (Level.begin (), Level.end (), -1);
            Level[s] = 0;
            Q.push (s);
            if (!bfs ())
                break;
            fill (Ptr.begin (), Ptr.end (), 0);
            while (int_fast64_t pushed = dfs (s, Inf))
                f += pushed;
        }
        return f;
    }
};


int n, m, u, v, s, b, k;
Vi64 Value;
VVi64 Cost;
Vs Squads;
Vb Bases;
VVIp Bases_at;


int main () {
    fin >> n >> m;
    Cost.assign (n + 1, Vi64 (n + 1, Inf));
    for (int i = 1; i <= n; ++ i) Cost[i][i] = 0LL;
    for (int i = 1; i <= m; ++ i)
        fin >> u >> v, Cost[u][v] = Cost[v][u] = min (Cost[u][v], 1LL);

    for (int k = 1; k <= n; ++ k)
        for (int i = 1; i <= n; ++ i)
            for (int j = 1; j <= n; ++ j)
                Cost[i][j] = min (Cost[i][j], Cost[i][k] + Cost[k][j]);

    fin >> s >> b >> k;
    Value.resize (s + 1), Bases_at.resize (n + 1);
    Squads.resize (s + 1), Bases.resize (b + 1);
    for (int i = 1; i <= s; ++ i)
        fin >> Squads[i];
    for (int i = 1; i <= b; ++ i)
        fin >> Bases[i];

    sort (Bases.begin (), Bases.end ());
    for (int i = 1; i <= b; ++ i) {
        int pos = Bases[i].position;
        if (Bases_at[pos].empty () || Bases_at[pos].back ().second < Bases[i].oil)
            Bases_at[pos].emplace_back (Bases[i].defense, Bases[i].oil);
    }

    int source = 0, sink = s + 1;
    Dinic dinic (s + 2, source, sink);
    int_fast64_t ans = 0LL;
    for (int i = 1; i <= s; ++ i) {
        bool found = false;
        for (int p = 1; p <= n; ++ p) {
            if (Cost[Squads[i].position][p] > Squads[i].fuel)
                continue;
            auto it = upper_bound (Bases_at[p].begin (), Bases_at[p].end (), make_pair (Squads[i].strength, Inf));
            if (it != Bases_at[p].begin ())
                -- it, found = true, Value[i] = max (Value[i], it->second);
        }
        Value[i] -= Squads[i].price;
        if (!found)
            Value[i] = -Inf;
        if (Value[i] >= 0)
            ans += Value[i], dinic.add_edge (source, i, Value[i]);
        else
            dinic.add_edge (i, sink, -Value[i]);
    }

    for (int i = 1; i <= k; ++ i)
        fin >> u >> v,
        dinic.add_edge (u, v, Inf);

    fout << ans - dinic.max_flow ();

    fin.close (), fout.close ();
    return 0;
}