/*

sap

Memory 328K

Time  454MS

*/

#include <iostream>

#include <queue>

using namespace std;

#define MAXV 110

#define INF 1<<29

#define min(a,b) (a>b?b:a)

int n,c[MAXV][MAXV],r[MAXV][MAXV],source,sink;

int dis[MAXV],maxflow;

void bfs(){

int v,i;

queue <int>q;

memset(dis,0,sizeof(dis));//sink超级汇点,source是超级源点。分层时从汇点开始

q.push(sink);

while(!q.empty()){

v=q.front();q.pop();

for(i=0;i<=sink;i++){

if(!dis[i] && c[i][v]>0){//有向边，

dis[i] = dis[v] +1;

q.push(i);

}

}

}

}

void sap(){

int top=source,pre[MAXV],i,j,low[MAXV];

//寻找增广路时，从源点开始

bfs(); //分层

memset(low,0,sizeof(low)); //保存路径的最小流量

while(dis[source]<n)//不一定是n，哪怕改成n+3也没事

{

low[source]=INF;

for(i=0;i<=sink;i++)

{ //找到一条允许弧

if(r[top][i]>0 && dis[top]==dis[i] +1) break;

}

if(i<=sink){ //找到一条就更新pre

low[i]=min(r[top][i],low[top]); //更新最小流量

pre[i]=top;top=i; //记录增广路径

if(top==sink){ //找到一条增广路径更新残量，否则继续寻找增广路的下一条边

maxflow += low[sink];

j = top;

while(j != source){

i=pre[j];

r[i][j]-=low[sink];//r数组是残留值，c是总值

r[j][i]+=low[sink];

j=i;

}

top=source; //再从头找一条增广路径

memset(low,0,sizeof(low));

}

}

else{ //找不到这样一条允许弧，i=sink+1。按理说找到第n层点后，遍历该点所有点，一定能找到第N+1层点，找不到，说明已经被减去，因此最小的X+1代替。必须选最小的，因为要保证最短路，选大点的则会走更长的路

int mindis=INF; 

for(j=0;j <=sink;j++){//在与top相连的J节点当中，找到dis[j]+1最小的那个，赋值给top,这样返回到上面时，dis[top]==dis[i] +1，找到最小的d[i]

if(r[top][j]>0 && mindis>dis[j] +1)

mindis=dis[j] +1;

}

dis[top]=mindis;

if(top!=source) top=pre[top];//这一行必须要加上，在top找不到下层节点后，对top点进行层数的修改后，继续搜索这条增广路（同dinic，而不是折回去从头找）：但必须接下来搜索top的前一个（pre[top]）节点的下一层节点，而不是接着按top搜索，因为如果top周围没有相连的节点（dis[top]被赋值为无限大，说明此点不会出现在增广路中，以后不用考虑），接下来的while循环会继续搜索top周围的点，从而无限循环。通过pre【top]可以避免无限循环。退回到pre[top]后如果能从别的路找到top层另一个节点并且能构成通路则优先这条路，否则走top层中层数被修改的这条路走。另一方面，退到source节点时，只要还能通过降低top的方式找到下一层节点，那么说明还存在增广路，如果source节点周围没有相连的了，则dis[top]=无限大，如果不可能有增广路，结束。

}

}

}

int main(){

int i,nedges,power_stations,consumers;

int x,y,z;

char ch;

while(scanf("%d%d%d%d", &n, &power_stations,&consumers,&nedges)!= EOF){

//Init

memset(r,0,sizeof(r));

memset(c,0,sizeof(c));

source=0;sink=n+1;n+=2;maxflow=0;

//Read Gragh

for(i=1;i<=nedges;i++){ //设置读图从1开始

cin>>ch>>x>>ch>>y>>ch>>z;

c[x+1][y+1]=r[x+1][y+1]=z;

}

//Build Gragh

//建立超级源点指向所有的发电站

for (i=1;i<=power_stations;i++){

cin>>ch>>x>>ch>>y;

c[source][x+1]=r[source][x+1]=y;

}

//建立超级汇点，使所有消费者指向它

for (i=1;i<=consumers;i++){

cin>>ch>>x>>ch>>y;

c[x+1][sink]=r[x+1][sink]=y;

}

sap();

printf("%d\n",maxflow);

}

return 0;

}

maxflow1459sap