#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=10000;
const int oo=2000000007;
struct edge{
int u,v,cap,next;
}E[N+N];
int n, L, R, e, ei;
int w[N], can[N], last[N];
vector<vector<int> > cg;
void addEdge(int u,int v, int cap){
E[ei++] = {u,v,cap,last[u]};
last[u] = ei-1;
E[ei++] = {v,u,0,last[v]};
last[v] = ei-1;
}
int low[N],idx[N], comp[N], id;
int val[N];
bool vis[N];
vector<int> S;
int dfs;
int findSCC(int u){
S.push_back(u);
vis[u] = true;
low[u] = idx[u] = ++dfs;
int minVal = oo;
for(auto &v:cg[u]){
if(low[v]==0)
minVal = min(minVal, findSCC(v));
if(vis[v])
low[u] = min(low[u], low[v]);
else
minVal = min(minVal, val[comp[v]]);
}
if(low[u] == idx[u]){
val[id] = minVal;
while(true){
int x=S.back();
S.pop_back();
vis[x] = false;
comp[x] = id;
if(x >= L && can[x] > 0)
val[id] = min(val[id], w[x]);
if(x == u)
break;
}
return val[id++];
}
return minVal;
}
int findLeft(){
cg.resize(n);
for(auto &e:cg)
e.clear();
for(int i=0;i<ei;++i)
if(E[i].cap > 0){
cg[E[i].u].push_back(E[i].v);
}
memset(low,0,sizeof(low));
dfs = 0;
id = 0;
for(int i=0;i<n;++i)
if(low[i] == 0)
findSCC(i);
int at = -1, best = oo;
for(int i=0;i<L;++i){
if(can[i]==0)
continue;
int cur = val[comp[i]];
if(cur == oo)
continue;
int total = w[i] + cur;
if (best > total){
best = total;
at = i;
}
}
return at;
}
int q[N], qf,ql;
int p[N];
pair<int,int> findRightAndFlow(int src) {
q[qf=ql=0] = src;
memset(p, -1, sizeof(p));
int best = oo, at = -1;
p[src] = src;
while(qf<=ql){
int u=q[qf++];
for(int e=last[u]; e!=-1; e=E[e].next){
if(E[e].cap == 0 || p[E[e].v] != -1)
continue;
p[E[e].v] = e;
q[++ql] = E[e].v;
if(E[e].v >= L && can[E[e].v] > 0){
if(best > w[E[e].v]){
best = w[E[e].v];
at = E[e].v;
}
}
}
}
assert(at != -1);
int flow = min(can[src], can[at]);
for(int cur=at; cur != src; cur = E[p[cur]].u){
flow = min(flow, E[p[cur]].cap);
}
can[src] -= flow;
can[at] -= flow;
for(int cur=at; cur != src; cur = E[p[cur]].u){
E[p[cur]].cap -= flow;
E[p[cur] ^ 1].cap += flow;
}
return {at, flow};
}
pair<int,ll> minCostMaxFlow() {
pair<int,ll> ret;
int paths = 0;
while(true) {
int left = findLeft();
if(left == -1)
break;
auto cur = findRightAndFlow(left);
ret.first += cur.second;
ret.second += cur.second * (ll)(w[left] + w[cur.first]);
++paths;
}
fprintf(stderr, "paths = %d", paths);
return ret;
}
int main() {
scanf("%d%d%d",&L, &R, &e);
n = L + R;
memset(last,-1,sizeof(last));
for(int i=0;i<n;++i)
scanf("%d%d",&can[i], &w[i]);
for(int i=0,a,b;i<e;++i){
scanf("%d%d",&a,&b);
--a;--b;
addEdge(a,b+L, oo);
}
auto ret = minCostMaxFlow();
printf("%d %lld\n",ret.first, ret.second);
return 0;
}
Copy