# [The 2009 ACM-ICPC Asia Harbin Regional Contest]D.Gold Mines

CODE:

#include <iostream>

#include <algorithm>

#include <string>

#include <cstring>

#include <cassert>

using namespace std;

#define oo 0x7f7f7f7f

#define MAXEDGE 510000

#define MAXV 1002

typedef struct struct_edge* edge;

struct struct_edge{int v,c,d;edge n,b;};

struct_edge pool[MAXEDGE];

edge top;

int S,T,V;

int q[MAXV];

bool inq[MAXV];

edge p[MAXV];

int d[MAXV];

void add_edge(int u,int v,int c,int d)

{

}

int min_cost_flow(int n,int t)

{

int flow=0,cost=0;

for (;;)

{

memset(d,oo,sizeof(d));

d[S]=0;

p[S]=0;

{

int u;

if (i->c&&d[i->v]>d[u]+i->d)

{

if (!inq[i->v])

inq[q[(++tail)%MAXV]=i->v]=true;

d[i->v]=d[u]+i->d;

p[i->v]=i;

}

}

if (d[T]==oo) break;

else

{

int delta=oo;

for (edge i=p[T];i;i=p[i->b->v])

if (delta>i->c) delta=i->c;

for (edge i=p[T];i;i=p[i->b->v])

i->c-=delta,i->b->c+=delta;

flow+=delta;

cost+=d[T]*delta;

}

}

if (flow!=n) return 1+t;

return cost;

}

int E;

int u[MAXEDGE],v[MAXEDGE];

int n;

int mine[MAXV];

int price[MAXV];

bool source[MAXV];

int total_price;

int result(int t)

{

if (t)

{

if (t==n)

{

source[0]=true;

int get=result(t-1);

source[0]=false;

}

else

{

int k=n-t;

while (k) if (source[i++]) k–;

while (i<n*2)

{

if (!source[i])

{

source[i]=true;

int get=result(t-1);

source[i]=false;

}

i++;

}

}

}

else

{

top=pool;

S=V+V,T=V+V+1;

for (int i=0;i<E;i++)

for (int i=0;i<V;i++)

for (int i=0;i<n*2;i++)

}

}

int main()

{

int T;

cin>>T;

for (int t=0;t<T;t++)

{

cin>>V>>E;

for (int i=0;i<E;i++)

cin>>u[i]>>v[i];

cin>>n;

for (int i=0;i<n*2;i++) cin>>mine[i];

total_price=0;

for (int i=0;i<V;i++) cin>>price[i],total_price+=price[i];

cout<<result(n)<<endl;

}

}