Dyson

#include <bits/stdc++.h>

using namespace std;

using Ip = pair <int, int>;
using Vip = vector <Ip>;
using Vi = vector <int>;
using V2i = vector <Vi>;
using Vi64 = vector <int64_t>;
using Qi = queue <int>;
constexpr int64_t Inf = 1LL * numeric_limits <int>::max ();

ifstream fin("dyson.in");
ofstream fout("dyson.out");

template <class T = int64_t>
class Dinic {
public:
    Dinic(int n, int s, int t):
        V(n), Source(s), Sink(t) {
        Adj.resize(V), Level.resize(V), Ptr.resize(V);
    }
    void addEdge(int u, int v, T cap) {
        if(u == v)
            return;
        Edges.emplace_back(u, v, cap);
        Adj[u].emplace_back((int)Edges.size () - 1);
        Edges.emplace_back(v, u, 0);
        Adj[v].emplace_back((int)Edges.size () - 1);
    }
    T maxFlow() {
        T flow = 0;
        while(true) {
            fill(Level.begin (), Level.end(), -1);
            Level[Source] = 0, Q.push(Source);
            if(!bfs()) break;
            fill(Ptr.begin (), Ptr.end(), 0);
            while(T pushed = dfs (Source, Inf))
                flow += pushed;
        }
        return flow;
    }
private:
    class FlowEdge {
    public:
        FlowEdge(int from, int to, T capacity):
            from(from), to(to), capacity(capacity) {
        }
    private:
        int from, to;
        T capacity, flow = 0;
        friend Dinic;
    };
    using Vf = vector <FlowEdge>;
    Vf Edges;
    V2i Adj;
    int V, Source, Sink;
    Vi Level, Ptr;
    Qi Q;
    bool bfs() {
        while(!Q.empty()) {
            int v = Q.front();
            Q.pop();
            for(const auto& it: Adj[v]) {
                if(Level[Edges[it].to] != -1 || Edges[it].capacity - Edges[it].flow < 1LL)
                    continue;
                Level[Edges[it].to] = Level[v] + 1;
                Q.push(Edges[it].to);
            }
        }
        return Level[Sink] != -1;
    }
    T dfs(int v, T pushed) {
        if(!pushed)
            return 0;
        if(v == Sink)
            return pushed;
        for(int& cit = Ptr[v]; cit < (int)Adj[v].size(); ++cit) {
            int it = Adj[v][cit], u = Edges[it].to;
            if(Level[u] != Level[v] + 1 || Edges[it].capacity - Edges[it].flow < 1LL)
                continue;
            T send = dfs(u, min(pushed, Edges[it].capacity - Edges[it].flow));
            if(!send)
                continue;
            Edges[it].flow += send;
            Edges[it ^ 1].flow -= send;
            return send;
        }
        return 0;
    }
};

int n, m, k, q, u, v;
int64_t w;
Vip Special;
Vi64 Val, Cut, DP;

inline void DFS(int edge, int mask, Dinic <int64_t>& Graph, int64_t flow) {
    if(edge == k)
        Cut[mask] = flow;
    else {
        int u = Special[edge].first, v = Special[edge].second;
        // case ON
        {
            auto NGraph = Graph;
            NGraph.addEdge(0, u, Inf), NGraph.addEdge(v, n - 1, Inf);
            int64_t nflow = flow + NGraph.maxFlow();
            DFS(edge + 1, mask | (1 << edge), NGraph, nflow);
        }
        // case OUT
        {
            Graph.addEdge(u, v, Inf);
            int64_t nflow = flow + Graph.maxFlow();
            DFS(edge + 1, mask, Graph, nflow);
        }
    }
}

int main() {
    fin >> n >> m >> k >> q;
    Special.resize(k), Val.resize(k), Cut.assign(1 << k, 0), DP.assign(1 << k, 0);
    Dinic <int64_t> Graph(n, 0, n - 1);
    for(int i = 0; i < m; ++i) {
        fin >> u >> v >> w;
        --u, --v;
        if(i < k)
            Special[i] = make_pair(u, v);
        else
            if(w)
                Graph.addEdge(u, v, w);
    }

    int64_t baseFlow = Graph.maxFlow();
    DFS(0, 0, Graph, baseFlow);
    for(int i = 1; i <= q; ++ i) {
        int64_t ans = Inf;
        for(int i = 0; i < k; ++ i)
            fin >> Val[i];
        for(int i = 0; i < k; ++ i)
            for(int j = 0; j < (1 << i); ++j)
                DP[j | (1 << i)] = DP[j] + Val[i];
        for(int i = 0; i < (1 << k); ++i)
            ans = min(ans, DP[i] + Cut[i]);
        fout << ans << "\n";
    }
    fin.close(), fout.close();
    return 0;
}