Dyson_5p

/// https://codeforces.com/problemset/problem/1383/F
#include<bits/stdc++.h>
#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int maxn=2e4+10,mod=1e9+7,inf=1e9+10;

struct Flow
{
    int cap[maxn];
    int mark[maxn],colo=0,h[maxn],pp[maxn],to[maxn],tp[maxn],nxt[maxn],qu[maxn],C = 0;
    Flow()
    {
        memset(tp,-1,sizeof tp);
    }
    void add_edge(int a,int b,int c)
    {
        nxt[C]=tp[a],cap[C]=c,to[C]=b,tp[a]=C;
        ++C;
        nxt[C]=tp[b],cap[C]=0,to[C]=a,tp[b]=C;
        ++C;
    }
    bool bfs(int src,int snk)
    {
        memset(h,-1,sizeof h);
        int L=0,R=1;
        qu[0]=src;
        h[src]=0;
        while(L<R)
        {
            int u=qu[L++];
            if(u==snk)
                return 1;
            for(int id=tp[u];id!=-1;id=nxt[id])
                if(h[to[id]]==-1&&cap[id]!=0)
                    h[to[id]]=1+h[u],qu[R++]=to[id];
        }
        return 0;
    }
    int dfs(int u,int snk,int f)
    {
        if(u==snk)
            return f;
        int ans=0;
        while(pp[u]!=-1)
        {
            int id=pp[u];
            if(cap[id]!= 0&&h[u]+1==h[to[id]])
            {
                int num=dfs(to[id],snk,min(f-ans,cap[id]));
                ans+=num;
                cap[id]-=num,cap[id^1]+=num;
                if(ans==f)
                    break;
            }
            pp[u]=nxt[pp[u]];
        }
        return ans;
    }
    int flow(int src,int snk)
    {
        int ans=0;
        while(bfs(src,snk))
        {
            memcpy(pp,tp,sizeof tp);
            ans+=dfs(src,snk,inf);
        }
        return ans;
    }
    int FLW[maxn],pr[maxn];
    int bfs2(int src,int snk)
    {
        int L=0,R=1;
        mark[src]=colo;
        qu[0]=src;
        FLW[src]=inf;
        while(L<R&&mark[snk]!=colo)
        {
            int u=qu[L++];
            for(int id=tp[u];id!=-1;id=nxt[id])
            {
                int y=to[id];
                if(mark[y]!=colo&&cap[id]!= 0)
                {
                    mark[y]=colo,FLW[y]=min(FLW[u],cap[id]),pr[y]=id,qu[R++]=y;
                    if(y==snk)
                        break;
                }
            }
        }
        if(mark[snk]!=colo)
            return 0;
        int ans=FLW[snk];
        while(snk!=src)
        {
            int id=pr[snk];
            cap[id]-=ans,cap[id^1]+=ans;
            snk=to[id^1];
        }
        return ans;
    }
    int dfs2(int u,int snk,int f)
    {
        mark[u]=colo;
        if(u==snk)
            return f;
        for(int id=tp[u];id!=-1;id=nxt[id])
        {
            if(cap[id]==0||mark[to[id]]==colo)
                continue;
            int num=dfs2(to[id],snk,min(f,cap[id]));
            if(num!=0)
            {
                cap[id]-=num,cap[id^1]+=num;
                return num;
            }
        }
        return 0;
    }
    int flow2(int src,int snk)
    {
        int ans=0;
        while(true)
        {
            ++colo;
            int num=bfs2(src,snk);
            if(num==0)
                break;
            ans+=num;
        }
        return ans;
    }
};

const int maxk=10,MAX=25;
int ANS[(1<<maxk)+10],n,k;
Flow flw;
int CAP[maxk][maxn];

void go(int pos,int msk,int F)
{
    if(pos==k)
    {
        ANS[msk]=F;
        return;
    }
    memcpy(CAP[pos],flw.cap,sizeof CAP[pos]);
    go(pos+1,msk, F);
    flw.cap[2*pos]=MAX;
    go(pos+1,msk^(1<<pos),F+flw.flow2(0,n-1));
    memcpy(flw.cap,CAP[pos],sizeof CAP[pos]);
}

int arr[maxk],sm[1<<maxk];
int main()
{
    ifstream fin("dyson.in");
    int m,q;
    fin>>n>>m>>k>>q;
    for(int i=0;i<m;++i)
    {
        int a,b,c;
        fin>>a>>b>>c;
        --a,--b;
        flw.add_edge(a,b,c);
    }
    int F=flw.flow(0,n-1);
    go(0,0,F);
    ofstream fout("dyson.out");
    while(q--)
    {
        for(int i=0;i<k;++i)
            fin>>arr[i];
        int ans=inf;
        for(int msk=0;msk<(1<<k); ++msk)
        {
            if(msk==0)
                sm[msk]=0;
            else
                sm[msk]=arr[ __builtin_ctz(msk)]+sm[msk-(msk&-msk)];
            ans=min(ans,sm[msk]+ANS[((1<<k)-1)^msk ]);
        }
        fout<<ans<<'\n';
    }
    return 0;
}