#include #include #include #include using namespace std; #define inf (INT_MAX/2) #define NN 300 #define BIG_VALUE 10000 struct E { int v,rev,cap,cost; }; vector es[NN]; int nn,used[NN],dist[NN],pot[NN]; int prev[NN],prev_eid[NN]; int added[NN][NN]; void add_edge(int a, int b, int cap, int cost){ es[a].push_back((E){b,es[b].size()+(a==b),cap,cost}); es[b].push_back((E){a,es[a].size()-1,0,-cost}); } pair mcmf(int s, int t){ pair res; memset(pot,0,sizeof(pot)); while (1){ memset(used,0,sizeof(used)); memset(prev,-1,sizeof(prev)); for (int i=0;incost){ dist[e.v]=ncost; prev[e.v]=best; prev_eid[e.v]=i; } } } if (dist[t]==inf) break; for (int i=0;i>n0>>n1,n0|n1) { map items; nn=2+n0+n1; for (int i=0;i>v; add_edge(0,2+i,v,0); } for (int i=0;i>v; add_edge(2+n0+i,1,v,0); } cin>>m; for (int i=0;i>name>>cost; items[name]=cost; } memset(added,0,sizeof(added)); cin>>l; for (int i=0;i>i0>>i1>>num; --i0,--i1; int cost=0; for (int j=0;j>name; cost+=items[name]; } add_edge(2+i0,2+n0+i1,NN,BIG_VALUE-cost); added[i0][i1]=1; } for (int i=0;i r=mcmf(0,1); cout<