#include<stdio.h>#include<string.h>#include<stdlib.h>#include<queue>const int INF = 999999999;std::queue<int> q;int main(void){ int n,p,c,m; int i,j; int from,to,w; int u,v,f; int cap[110][110],flow[110][110]; int a[110],pre[110]; while( scanf("%d%d%d%d",&n,&p,&c,&m) != EOF ) { memset(cap,0,sizeof(cap)); memset(flow,0,sizeof(flow)); for( i = 0; i < m; i++ ) { scanf(" (%d,%d)%d",&from,&to,&w); cap[from][to] = w; } for( i = 1; i <= p; i++ ) { scanf(" (%d)%d",&to,&w); cap[n][to] = w; } for( i = 1; i <= c; i++ ) { scanf(" (%d)%d",&from,&w); cap[from][n+1] = w; } f= 0; while( 1 ) { memset(a,0,sizeof(a)); a[n] = INF; q.push(n); while( !q.empty() ) { u = q.front();q.pop(); for( v = 0; v <= n+1; v ++ ) if( !a[v] && cap[u][v] > flow[u][v] ) { pre[v] = u; q.push(v); if( a[u] < cap[u][v] - flow[u][v] ) a[v] = a[u]; else a[v] = cap[u][v] - flow[u][v]; } } if( a[n+1] == 0 ) break; for( u = n+1; u != n; u = pre[u] ) { flow[ pre[u] ][u] += a[n+1]; flow[u][ pre[u] ] -= a[n+1]; } f += a[n+1]; } printf("%dn",f); } return 0; }
