#include // #include using namespace std; // using namespace atcoder; template ostream &operator<<(ostream &os, const pair &p) { os << "(" << p.first << "," << p.second << ")"; return os; } #ifdef __LOCAL #define debug(x) cerr << __LINE__ << ": " << #x << " = " << (x) << '\n' #define debugArray(x, n) \ cerr << __LINE__ << ": " << #x << " = {"; \ for (long long hoge = 0; (hoge) < (long long)(n); ++(hoge)) \ cerr << ((hoge) ? "," : "") << x[hoge]; \ cerr << "}" << '\n' #define debugMatrix(x, h, w) \ cerr << __LINE__ << ": " << #x << " =\n"; \ for (long long hoge = 0; (hoge) < (long long)(h); ++(hoge)) { \ cerr << ((hoge ? " {" : "{{")); \ for (long long fuga = 0; (fuga) < (long long)(w); ++(fuga)) \ cerr << ((fuga ? ", " : "")) << x[hoge][fuga]; \ cerr << "}" << (hoge + 1 == (long long)(h) ? "}" : ",") << '\n'; \ } #else #define debug(x) (void(0)) #define debugArray(x, n) (void(0)) #define debugMatrix(x, h, w) (void(0)) #endif template struct MaxFlow : public FlowAlgo { using FlowAlgo::FlowAlgo; using Edge = typename FlowAlgo::Edge; using flow_t = decltype(Edge::cap); int add_vertex() { return this->adj.resize(++this->n), this->n - 1; } std::vector add_vertices(const std::size_t size) { std::vector ret(size); std::iota(ret.begin(), ret.end(), this->n); return this->adj.resize(this->n += size), ret; } struct EdgePtr { friend class MaxFlow; MaxFlow *instance; int v, e; bool bidir; Edge &edge() { return instance->adj[v][e]; } Edge &rev() { Edge &e = edge(); return instance->adj[e.dst][e.rev]; } EdgePtr(MaxFlow *instance, int v, int e, bool d) : instance(instance), v(v), e(e), bidir(d) {} public: EdgePtr() = default; int src() { return v; } int dst() { return edge().dst; } bool is_direct() const { return !bidir; } flow_t flow() { return cap() - edge().cap; } flow_t cap() { return (edge().cap + rev().cap) / (1 + bidir); } flow_t change_cap(flow_t new_cap, int s, int t) { assert(0 <= new_cap); Edge &e = edge(), &re = rev(); flow_t diff = new_cap - cap(), extrusion = std::abs(flow()) - new_cap; if (extrusion <= 0) return e.cap += diff, re.cap += diff * bidir, 0; int sr = src(), ds = dst(); if (flow() < 0) std::swap(sr, ds); if (bidir) { if (sr == src()) re.cap += 2 * diff + e.cap, e.cap = 0; else e.cap += 2 * diff + re.cap, re.cap = 0; } else re.cap += diff; extrusion -= instance->maxflow(sr, ds, extrusion); if (ds != t) instance->maxflow(t, ds, extrusion); if (sr != s) instance->maxflow(sr, s, extrusion); return extrusion; } }; EdgePtr add_edge(int src, int dst, flow_t cap, bool bidir = false) { assert(0 <= src && src < this->n); assert(0 <= dst && dst < this->n); assert(0 <= cap); int e = this->adj[src].size(); int re = src == dst ? e + 1 : this->adj[dst].size(); this->adj[src].push_back(Edge{dst, re, cap}); this->adj[dst].push_back(Edge{src, e, cap * bidir}); return this->m++, EdgePtr{this, src, e, bidir}; } flow_t maxflow(int s, int t) { return maxflow(s, t, std::numeric_limits::max()); } flow_t maxflow(int s, int t, flow_t flow_lim) { return this->flow(s, t, flow_lim); } std::vector mincut(int s) { std::vector visited(this->n); static std::queue que; for (que.push(s); !que.empty();) { int p = que.front(); que.pop(), visited[p] = true; for (const auto &e : this->adj[p]) if (e.cap && !visited[e.dst]) visited[e.dst] = true, que.push(e.dst); } return visited; } }; template struct Dinic { Dinic(std::size_t _n = 0) : n(_n), m(0), adj(n) {} protected: struct Edge { int dst, rev; flow_t cap; }; int n, m; std::vector> adj; std::vector level, iter; inline void levelize(const int &s, const int &t) { level.assign(n, -1), level[s] = 0; std::queue que; for (que.push(s); !que.empty();) { int u = que.front(); que.pop(); for (auto &e : adj[u]) if (e.cap > 0 && level[e.dst] < 0) { level[e.dst] = level[u] + 1; if (e.dst == t) return; que.push(e.dst); } } } inline flow_t dfs(int u, const int &s, flow_t cur) { if (u == s) return cur; flow_t ret = 0; for (int &i = iter[u]; i < adj[u].size(); i++) { Edge &e = adj[u][i], &re = adj[e.dst][e.rev]; if (level[u] <= level[e.dst] || re.cap == 0) continue; flow_t f = dfs(e.dst, s, std::min(cur - ret, re.cap)); if (f <= 0) continue; e.cap += f, re.cap -= f, ret += f; if (ret == cur) return ret; } return level[u] = n, ret; } flow_t flow(int s, int t, flow_t flow_lim) { assert(0 <= s && s < n); assert(0 <= t && t < n); assert(s != t); flow_t ret = 0; for (flow_t f; ret < flow_lim; ret += f) { if (levelize(s, t), level[t] == -1) break; iter.assign(n, 0); if (!(f = dfs(t, s, flow_lim - ret))) break; } return ret; } }; template auto monge_mincut(int n, int k, Th theta, Ph phi) { static_assert(std::is_same_v); static constexpr T INF = std::numeric_limits::max(); T ret = 0; MF graph; int s = graph.add_vertex(), t = graph.add_vertex(); std::vector> x; std::vector> th(n, std::vector(k)); for (int i = 0; i < n; i++) { x.emplace_back(graph.add_vertices(k - 1)); for (int l = 1; l < k - 1; l++) graph.add_edge(x[i][l], x[i][l - 1], INF); for (int l = 0; l < k; l++) th[i][l] = theta(i, l); } for (int i = 0; i < n; i++) for (int j = i + 1; j < n; j++) { for (int l = 0; l < k - 1; l++) for (int m = 0; m < k - 1; m++) { T cost = -phi(i, j, l + 1, m + 1) + phi(i, j, l, m + 1) + phi(i, j, l + 1, m) - phi(i, j, l, m); assert(cost >= 0); // monge if (cost > 0) graph.add_edge(x[i][l], x[j][m], cost); } for (int l = 0; l < k; l++) th[i][l] += phi(i, j, l, k - 1); for (int l = 0; l < k; l++) th[j][l] += phi(i, j, 0, l); ret -= phi(i, j, 0, k - 1); } for (int i = 0; i < n; i++) { ret += th[i][0]; for (int l = 0; l < k - 1; l++) { T cost = th[i][l] - th[i][l + 1]; if (cost > 0) graph.add_edge(s, x[i][l], cost), ret -= cost; if (cost < 0) graph.add_edge(x[i][l], t, -cost); } } ret += graph.maxflow(s, t); auto y = graph.mincut(s); std::vector sol(n, k - 1); for (int i = 0; i < n; i++) for (int l = 0; l < k - 1; l++) if (!y[x[i][l]]) sol[i] = l, l = k; return std::make_pair(ret, sol); } signed main() { cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; vector B(N), C(N); for (int i = 0; i < N; i++) cin >> B[i] >> C[i]; int M; cin >> M; vector> to(N, vector(N, false)); for (int i = 0; i < M; i++) { int D, E; cin >> D >> E; to[D][E] = true; } const long long INF = LLONG_MAX; auto theta = [&](int i, int k) { if (k == 0) return -C[i]; if (k == 1) return 0ll; return -B[i]; }; auto phi = [&](int i, int j, int k, int l) { if (to[i][j] && k == 2 && l == 0) return INF; return 0ll; }; using MF = MaxFlow>; auto [ans, x] = monge_mincut(N, 3, theta, phi); cout << -ans << '\n'; return 0; }