/// 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
//Works for negative costs, but does not work for negative cycles
//Complexity: O(min(E^2 *V log V, E logV * flow))
struct Edge{
int u, v;
long long cap, cost;
Edge(int _u, int _v, long long _cap, long long _cost){
u = _u; v = _v; cap = _cap; cost = _cost;
}
};
struct MinCostFlow{
int n, s, t;
long long flow, cost;
vector<vector<int> > graph;
vector<Edge> e;
// if cost is double, dist should be double
vector<long long> dist;
vector<int> parent;
MinCostFlow(int _n){
// 0-based indexing
n = _n;
graph.assign(n, vector<int> ());
}
void addEdge(int u, int v, long long cap, long long cost, bool directed = true){
graph[u].push_back(e.size());
e.push_back(Edge(u, v, cap, cost));
graph[v].push_back(e.size());
e.push_back(Edge(v, u, 0, -cost));
if(!directed)
addEdge(v, u, cap, cost, true);
}
pair<long long, long long> getMinCostFlow(int _s, int _t){
s = _s; t = _t;
flow = 0, cost = 0;
while(SPFA()){
flow += sendFlow(t, 1LL<<62);
}
return make_pair(flow, cost);
}
// not sure about negative cycle
bool SPFA(){
parent.assign(n, -1);
dist.assign(n, 1LL<<62); dist[s] = 0;
vector<int> queuetime(n, 0); queuetime[s] = 1;
vector<bool> inqueue(n, 0); inqueue[s] = true;
queue<int> q; q.push(s);
bool negativecycle = false;
while(!q.empty() && !negativecycle){
int u = q.front(); q.pop(); inqueue[u] = false;
for(int i = 0; i < graph[u].size(); i++){
int eIdx = graph[u][i];
int v = e[eIdx].v; ll w = e[eIdx].cost, cap = e[eIdx].cap;
if(dist[u] + w < dist[v] && cap > 0){
dist[v] = dist[u] + w;
parent[v] = eIdx;
if(!inqueue[v]){
q.push(v);
queuetime[v]++;
inqueue[v] = true;
if(queuetime[v] == n+2){
negativecycle = true;
break;
}
}
}
}
}
return dist[t] != (1LL<<62);
}
long long sendFlow(int v, long long curFlow){
if(parent[v] == -1)
return curFlow;
int eIdx = parent[v];
int u = e[eIdx].u; ll w = e[eIdx].cost;
long long f = sendFlow(u, min(curFlow, e[eIdx].cap));
cost += f*w;
e[eIdx].cap -= f;
e[eIdx^1].cap += f;
return f;
}
};
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;
MinCostFlow flow(n+m+2);
f(i,0,n+m){
int x, y;
cin >> x >> y;
if(i<n){
flow.addEdge(src,i+1,x,y);
} else {
flow.addEdge(i+1,snk,x,y);
}
}
f(i,0,k) {
int x, y;
cin >> x >> y;
flow.addEdge(x,n+y,1e9,0);
}
auto ans = flow.getMinCostFlow(src,snk);
cout << ans.first << ' ' << ans.second << endl;
return 0;
}
Copy