Description

A power network consists of nodes (power stations, consumers and dispatchers) connected by power transport lines. A node u may be supplied with an amount s(u) >= 0 of power, may produce an amount 0 <= p(u) <= p_max(u) of power, may consume an amount 0 <= c(u) <= min(s(u),c_max(u)) of power, and may deliver an amount d(u)=s(u)+p(u)-c(u) of power. The following restrictions apply: c(u)=0 for any power station, p(u)=0 for any consumer, and p(u)=c(u)=0 for any dispatcher. There is at most one power transport line (u,v) from a node u to a node v in the net; it transports an amount 0 <= l(u,v) <= l_max(u,v) of power delivered by u to v. Let Con=Σ_uc(u) be the power consumed in the net. The problem is to compute the maximum value of Con.

An example is in figure 1. The label x/y of power station u shows that p(u)=x and p_max(u)=y. The label x/y of consumer u shows that c(u)=x and c_max(u)=y. The label x/y of power transport line (u,v) shows that l(u,v)=x and l_max(u,v)=y. The power consumed is Con=6. Notice that there are other possible states of the network but the value of Con cannot exceed 6.

Input

Output

Sample Input

2 1 1 2 (0,1)20 (1,0)10 (0)15 (1)207 2 3 13 (0,0)1 (0,1)2 (0,2)5 (1,0)1 (1,2)8 (2,3)1 (2,4)7         (3,5)2 (3,6)5 (4,2)7 (4,3)5 (4,5)1 (6,0)5         (0)5 (1)2 (3)2 (4)1 (5)4

Sample Output

156

Hint

//by:yuan
//2015.1.27
 1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 #include<vector> 7 using namespace std; 8 const int inf=0x3fffffff; 9 const int maxn=107;10 struct Edge11 {12     int from,to,cap,flow;13     Edge(int u,int v,int c,int f):from(u),to(v),cap(c),flow(f){}14 };15 int n,np,nc,m;16 vector<Edge> edges;17 vector<int> G[maxn];18 int a[maxn];19 int p[maxn];20 21 void init()22 {23     for(int i=0;i<=n+1;i++)24         G[i].clear();25     edges.clear();26 }27 void AddEdge(int from,int to,int cap)28 {29     int mm;30     edges.push_back(Edge(from,to,cap,0));31     edges.push_back(Edge(to,from,0,0));32     mm=edges.size();33     G[from].push_back(mm-2);34     G[to].push_back(mm-1);35 }36 int Maxflow(int s,int t)37 {38     int flow=0;39     for(;;){40         memset(a,0,sizeof(a));41         queue<int> Q;42         Q.push(s);43         a[s]=inf;44         while(!Q.empty()){45             int x=Q.front();Q.pop();46             for(int i=0;i<G[x].size();i++)47             {48                 Edge &e=edges[G[x][i]];49                 if(!a[e.to]&&e.cap>e.flow){50                     p[e.to]=G[x][i];51                     a[e.to]=min(a[x],e.cap-e.flow);52                     Q.push(e.to);53                 }54             }55             if(a[t]) break;56         }57         if(!a[t]) break;58         for(int u=t;u!=s;u=edges[p[u]].from){59             edges[p[u]].flow+=a[t];60             edges[p[u]^1].flow-=a[t];61         }62         flow+=a[t];63     }64     return flow;65 }66 int main()67 {  68     int u,v,c;69     while(~scanf("%d%d%d%d",&n,&np,&nc,&m)){70         init();71         for(int i=0;i<m;i++)72         {73             scanf(" (%d,%d)%d",&u,&v,&c);74             AddEdge(u+1,v+1,c);75         }76         for(int i=0;i<np;i++)77         {78            scanf(" (%d)%d",&u,&c);79             AddEdge(0,u+1,c);80         }81          for(int i=0;i<nc;i++)82         {  83            scanf(" (%d)%d",&u,&c);84             AddEdge(u+1,n+1,c);85         }86         int ans=Maxflow(0,n+1);87         printf("%d\n",ans);88     }89     return 0;90 }