帮忙卡个常

#pragma GCC diagnostic error "-std=c++14"
#pragma GCC target("avx")
#pragma GCC optimize(3)
#pragma GCC optimize("Ofast")
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<utility>
#include<bitset>
#include<cstdio>
#include<string>
#include<time.h>
#include<vector>
#include<cmath>
#include<queue>
#include<map>
#include<set>
using namespace std;
const int N=1e4+5,M=2e4+5,INF=25,L=1030,O=15;
int f[N],ne[M],t[M],w[L][M],b=1,v[N],d[N],n,k,a[L],g[O],s[L],l[L],T,S,c[N],e;
bool r[N];
char bu[1<<24];
inline char get()
{
    if(S==T)
    {
        S=0;
        T=fread(bu,1,1<<24,stdin);
        if(S==T)
            return EOF;
    }
    return bu[S++];
}
int read()
{
	int x=0;
	char c;
	do
		c=get();
	while(c<'0'||'9'<c);
	while('0'<=c&&c<='9')
	{
		x=(x<<3)+(x<<1)+(c^48);
		c=get();
	}
	return x;
}
void add(int x,int y,int z)
{
	ne[++b]=f[x];
	f[x]=b;
	t[b]=y;
	w[0][b]=z;
}
bool bfs()
{
	queue<int>q;
	q.push(1);
	memset(d,0,sizeof(d));
	d[1]=1;
	while(!q.empty())
	{
		v[q.front()]=f[q.front()];
		for(int i=f[q.front()];i;i=ne[i])
		{
			if(w[0][i]&&!d[t[i]])
			{
				d[t[i]]=d[q.front()]+1;
				q.push(t[i]);
			}
		} 
		q.pop();
	}
	return d[n]>0;
}
int dfs(int x,int m)
{
	if(x==n)
		return m;
	for(int i=v[x];i;i=ne[i])
	{
		v[x]=i;
		if(d[t[i]]==d[x]+1&&w[0][i])
		{
			int f=dfs(t[i],min(w[0][i],m));
			if(f)
			{
				w[0][i]-=f;
				w[0][i^1]+=f;
				return f;
			}
		}
	}
	return 0;
}
int dnc()
{
	int a=0;
	while(bfs())
	{
		int f;
		while(f=dfs(1,INF))
			a+=f;
	}
	return a;
}
int lb(int x)
{
	return -x&x;
}
int rdfs(int x,int m,int u)
{
	if(x==n)
		return m;
	r[x]=1;
	for(int i=f[x];i;i=ne[i])
		if(w[u][i]&&!r[t[i]])
		{
			int f=rdfs(t[i],min(w[u][i],m),u);
			if(f)
			{
				w[u][i]-=f;
				w[u][i^1]+=f;
				return f;
			}
		}
	return 0;
}
int main()
{
	int m,q,x,y,z,an;
	n=read(),m=read(),k=read(),q=read();
	for(int i=1;i<=m;i++)
	{
		x=read(),y=read(),z=read();
		add(x,y,z),add(y,x,0);
	}
	a[0]=dnc();
	l[1]=1;
	for(int i=2;i<(1<<k);i<<=1)
		l[i]=l[i>>1]+1;
	for(int i=1;i<(1<<k);i++)
	{
		for(int j=2;j<=b;j++)
			w[i][j]=w[i^lb(i)][j];
		w[i][l[lb(i)]<<1]=INF;
		a[i]=a[i^lb(i)];
		memset(r,0,sizeof(r));
		while(z=rdfs(1,INF,i))
		{
			a[i]+=z;
			memset(r,0,sizeof(r));
		}
	}
	for(int i=1;i<=q;i++)
	{
		an=1e9;
		for(int j=1;j<=k;j++)
			g[j]=read();
		for(int j=1;j<(1<<k);j++)
			s[j]=s[j^lb(j)]+g[l[lb(j)]];
		for(int j=0;j<(1<<k);j++)
			an=min(an,s[j]+a[((1<<k)-1)^j]);
		printf("%d\n",an);
	}
}