#define _CRT_SECURE_NO_WARNINGS
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define endl "\n"
#define ll long long
#define sz(s) (int)(s.size())
#define INF 0x3f3f3f3f3f3f3f3fLL
#define all(v) v.begin(),v.end()
#define watch(x) cout<<(#x)<<" = "<<x<<endl
const int dr[]{ -1, -1, 0, 1, 1, 1, 0, -1 };
const int dc[]{ 0, 1, 1, 1, 0, -1, -1, -1 };
#if __cplusplus >= 201402L
template<typename T>
vector<T> create(size_t n) {
return vector<T>(n);
}
template<typename T, typename ... Args>
auto create(size_t n, Args ... args) {
return vector<decltype(create<T>(args...))>(n, create<T>(args...));
}
#endif
void run() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.in", "r", stdin);
#else
#endif
}
struct MCMF {
struct edge {
int from, to, cost, cap, flow, backEdge;
edge() {
from = to = cost = cap = flow = backEdge = 0;
}
edge(int from, int to, int cost, int cap, int flow, int backEdge) :
from(from), to(to), cost(cost), cap(cap), flow(flow), backEdge(
backEdge) {
}
bool operator <(const edge& other) const {
return cost < other.cost;
}
};
int n, src, dest;
vector<vector<edge>> adj;
const int OO = (int)INF;
MCMF(int n, int src, int dest) :
n(n), src(src), dest(dest), adj(n) {
}
void addEdge(int u, int v, int cost, int cap) {
edge e1 = edge(u, v, cost, cap, 0, adj[v].size());
edge e2 = edge(v, u, -cost, 0, 0, adj[u].size());
adj[u].push_back(e1);
adj[v].push_back(e2);
}
pair<int, ll> minCostMaxFlow() {
int maxFlow = 0;
ll cost = 0;
while (true) {
vector<pair<int, int>> path = spfa();
if (path.empty())
break;
int new_flow = OO;
for (auto& it : path) {
edge& e = adj[it.first][it.second];
new_flow = min(new_flow, e.cap - e.flow);
}
for (auto& it : path) {
edge& e = adj[it.first][it.second];
e.flow += new_flow;
cost += 1LL * new_flow * e.cost;
adj[e.to][e.backEdge].flow -= new_flow;
}
maxFlow += new_flow;
}
return { maxFlow,cost };
}
enum visit {
finished, in_queue, not_visited
};
vector<pair<int, int>> spfa() {
vector<int> dis(n, OO), prev(n, -1), from_edge(n), state(n,
not_visited);
deque<int> q;
dis[src] = 0;
q.push_back(src);
while (!q.empty()) {
int u = q.front();
q.pop_front();
state[u] = finished;
for (int i = 0; i < adj[u].size(); i++) {
edge e = adj[u][i];
if (e.flow >= e.cap || dis[e.to] <= dis[u] + e.cost)
continue;
dis[e.to] = dis[u] + e.cost;
prev[e.to] = u;
from_edge[e.to] = i;
if (state[e.to] == in_queue)
continue;
if (state[e.to] == finished
|| (!q.empty() && dis[q.front()] > dis[e.to]))
q.push_front(e.to);
else
q.push_back(e.to);
state[e.to] = in_queue;
}
}
if (dis[dest] == OO)
return {};
vector<pair<int, int>> path;
int cur = dest;
while (cur != src) {
path.push_back({ prev[cur], from_edge[cur] });
cur = prev[cur];
}
reverse(path.begin(), path.end());
return path;
}
};
int main() {
run();
int n, m, k;
cin >> n >> m >> k;
int src = 0, dest = n + m + 1;
MCMF flow(dest + 1, src, dest);
vector<int> v(n + 1), v2(m + 1);
for (int i = 1; i <= n; i++) {
int match;
cin >> match >> v[i];
flow.addEdge(src, i, 0, match);
}
for (int i = 1; i <= m; i++) {
int match;
cin >> match >> v2[i];
flow.addEdge(n + i, dest, 0, match);
}
while (k--) {
int x, y;
cin >> x >> y;
flow.addEdge(x, y + n, v[x] + v2[y], INF);
}
pair<int, int> p = flow.minCostMaxFlow();
cout << p.first << ' ' << p.second << endl;
}
Copy