#include <bits/stdc++.h>   using namespace std;   const int maxn = 10000;   const int maxm = 20000;   const int maxk = 10;   const int inf = 25;   int tot_edge, sz;   int head[maxn];   int nxt[maxm];   int to[maxm];   int cap[maxm];   int flow[maxk + 1][maxm];   int qu[maxn];   int prv[maxn];   int when[maxn];   int pass_flow[maxn];   int last_time;   int level[maxn], edge_pos[maxn];   int read() {     int xx = 0, ff = 1;     char ch = getchar();     while (ch >  9  || ch <  0 ) {       if (ch ==  - ) ff = -1;       ch = getchar();     }     while (ch >=  0  && ch <=  9 ) {       xx = (xx << 3) + (xx << 1) + ch -  0 ;       ch = getchar();     }     return xx * ff;   }   void add_edge(int u, int v, int w) {     nxt[tot_edge] = head[u];     head[u] = tot_edge;     to[tot_edge] = v;     cap[tot_edge] = w;     tot_edge++;   }   bool bfs(int s, int t, int *flow) {     sz = 0;     qu[sz++] = t;     int pnt = 0;     memset(level, -1, sizeof(level));     level[t] = 0;     while (pnt < sz && level[s] == -1) {       int u = qu[pnt++];       for (int e = head[u]; e >= 0; e = nxt[e]) {         int v = to[e];         if (level[v] == -1 && flow[e ^ 1] < cap[e ^ 1]) {           level[v] = level[u] + 1;           qu[sz++] = v;         }       }     }     return level[s] != -1;   }   int dinic(int s, int t, int *flow) {     int ret = 0;     while (bfs(s, t, flow)) {       copy(head, head + maxn, edge_pos);       function<int(int, int)> find_path = [&](int u, int res) {         if (u == t) return res;         for (int &e = edge_pos[u]; e >= 0; e = nxt[e]) {           int v = to[e];           if (flow[e] == cap[e] || level[u] - 1 != level[v]) continue;           int push = find_path(v, min(res, cap[e] - flow[e]));           if (push > 0) {             flow[e] += push;             flow[e ^ 1] -= push;             if (flow[e] == cap[e]) e = nxt[e];             return push;           }         }         return 0;       };       for (int f; (f = find_path(s, 1e9)) > 0;) ret += f;     }     return ret;   }   int augment(int s, int t, int *flow) {     last_time++;     sz = 0;     qu[sz++] = s;     when[s] = last_time;     int pnt = 0;     pass_flow[s] = inf;     pass_flow[t] = 0;     while (pnt < sz && when[t] != last_time) {       int u = qu[pnt++];       assert(pass_flow[u] > 0);       for (int e = head[u]; e >= 0; e = nxt[e]) {         int v = to[e];         if (when[v] != last_time && flow[e] < cap[e]) {           pass_flow[v] = min(pass_flow[u], cap[e] - flow[e]);           prv[v] = e;           when[v] = last_time;           qu[sz++] = v;           if (v == t) break;         }       }     }     int f = pass_flow[t];     if (f == 0) return f;     do {       int e = prv[t];       flow[e] += f;       flow[e ^ 1] -= f;       assert(to[e] == t);       t = to[e ^ 1];     } while (t != s);     return f;   }   int max_flow(int s, int t, int *flow) {     int res = 0, cur = 0;     do {       cur = augment(s, t, flow);       res += cur;     } while (cur);     return res;   }   int n, m, k, q;   int masked[1 << maxk];   void go(int n, int m, int mask, int pointer) {     for (int i = 0; (mask >> i & 1) == 0 && i < k; ++i) {       int n_mask = mask | (1 << i);       copy(flow[pointer], flow[pointer] + m, flow[pointer + 1]);       cap[2 * i] = inf;       masked[n_mask] = masked[mask] + max_flow(0, n - 1, flow[pointer + 1]);       go(n, m, n_mask, pointer + 1);       cap[2 * i] = 0;     }   }   int wei[maxk];   int suma[1 << maxk];   int eptr;   struct info {     int u, v, w;   } edges[maxm];   vector<int> adj[maxn];   void relabel(int n, int m) {     sz = 0;     qu[sz++] = 0;     int pnt = 0;     memset(level, -1, sizeof(level));     level[0] = 0;     level[n - 1] = n - 1;     while (pnt < sz) {       int u = qu[pnt++];       for (auto v : adj[u]) {         if (level[v] == -1) {           level[v] = sz;           qu[sz++] = v;         }       }     }     for (int i = 0; i < n; ++i)       if (level[i] == -1) level[i] = sz++;     for (int i = 0; i < m; ++i) {       edges[i].u = level[edges[i].u];       edges[i].v = level[edges[i].v];     }   }   int main() {     memset(head, -1, sizeof head);     n = read();     m = read();     k = read();     q = read();     for (int i = 0; i < m; ++i) {       int u, v, w;       u = read();       v = read();       w = read();       u--;       v--;       edges[i] = {u, v, w};       adj[u].push_back(v);     }     relabel(n, m);     for (int i = 0; i < m; ++i) {       add_edge(edges[i].u, edges[i].v, edges[i].w);       add_edge(edges[i].v, edges[i].u, 0);     }     masked[0] = dinic(0, n - 1, flow[0]);     go(n, 2 * m, 0, 0);     int top = (1 << k) - 1;     for (int i = 0; i < q; ++i) {       for (int j = 0; j < k; ++j) wei[j] = read();       int answer = masked[top];       for (int j = 1; j < (1 << k); j++) {         int x = __builtin_ctz(j);         suma[j] = suma[j ^ (1 << x)] + wei[x];         answer = min(answer, masked[top ^ j] + suma[j]);       }       printf( %d n , answer);     }     return 0;   }   