/// Fuck Them, Fuck Me, and Fuck You
#pragma GCC optimize("O3")
#pragma GCC optimize ("unroll-loops")
#pragma GCC target("avx,avx2,fma")
#include "bits/stdc++.h"
using namespace std;
using ll = long long;
using ii = pair<int, int>;
#define pb push_back
#define F first
#define S second
#define f(i,a,b) for(int i = a; i < b; i++)
#define all(a) a.begin(),a.end()
#define rall(a) a.rbegin(),a.rend()
const int N = 1e6 + 5, LG = 19, MOD = 1e9 + 7;
#define int ll
int mL[10005];
int mR[10005];
int wL[10005];
int wR[10005];
vector<int> edges[20005];
namespace mcmf{
const int MAX = 1000010;
const int INF = 1 << 25;
int cap[MAX], flow[MAX], cost[MAX], dis[MAX];
int n, m, s, t, Q[10000010], adj[MAX], link[MAX], last[MAX], from[MAX], visited[MAX];
void init(int nodes, int source, int sink){
m = 0, n = nodes, s = source, t = sink;
for (int i = 0; i <= n; i++) last[i] = -1;
}
void addEdge(int u, int v, int c, int w){
adj[m] = v, cap[m] = c, flow[m] = 0, cost[m] = +w, link[m] = last[u], last[u] = m++;
adj[m] = u, cap[m] = 0, flow[m] = 0, cost[m] = -w, link[m] = last[v], last[v] = m++;
}
bool spfa(){
int i, j, x, f = 0, l = 0;
for (i = 0; i <= n; i++) visited[i] = 0, dis[i] = INF;
dis[s] = 0, Q[l++] = s;
while (f < l){
i = Q[f++];
for (j = last[i]; j != -1; j = link[j]){
if (flow[j] < cap[j]){
x = adj[j];
if (dis[x] > dis[i] + cost[j]){
dis[x] = dis[i] + cost[j], from[x] = j;
if (!visited[x]){
visited[x] = 1;
if (f && rand() & 7) Q[--f] = x;
else Q[l++] = x;
}
}
}
}
visited[i] = 0;
}
return (dis[t] != INF);
}
// we can return all the flow values for each edge from this function
// vi solve()
pair <int, int> solve(){
int i, j;
int mincost = 0, maxflow = 0;
while (spfa()){
int aug = INF;
for (i = t, j = from[i]; i != s; i = adj[j ^ 1], j = from[i]){
aug = min(aug, cap[j] - flow[j]);
}
for (i = t, j = from[i]; i != s; i = adj[j ^ 1], j = from[i]){
flow[j] += aug, flow[j ^ 1] -= aug;
}
maxflow += aug, mincost += aug * dis[t];
}
// edges are indexed from 0 to m
// vi ret(flow,flow+m)
// to find flow of a specific edge, we just noticed that flow[2*i] contains
// the flow amount in i-th edge
return make_pair(mincost, maxflow);
}
}
int32_t main(){
#ifdef ONLINE_JUDGE
ios_base::sync_with_stdio(0);
cin.tie(0);
#endif // ONLINE_JUDGE
int n, m, k;
cin >> n >> m >> k;
int sumL = 0, sumR = 0;
int src = 0, snk = n + m + 1;
mcmf::init(n+m+2,src,snk);
f(i,0,n+m){
int x, y;
cin >> x >> y;
if(i<n){
mcmf::addEdge(src,i+1,x,y);
} else {
mcmf::addEdge(i+1,snk,x,y);
}
}
f(i,0,k) {
int x, y;
cin >> x >> y;
mcmf::addEdge(x,n+y,1e9,0);
}
auto ans = mcmf::solve();
cout << ans.second << ' ' << ans.first << endl;
return 0;
}
Copy