#include <bits/stdc++.h>
#pragma GCC optmize("Ofast")
using namespace std;
const int maxn = 20009;
const int inf = 1e8;
int n, m, K, T;
int e[1 << 10][maxn << 1];
int head[maxn], cntedge = 1;
int from[maxn], to[maxn], cap[maxn], flow[maxn], nex[maxn];
void Addedge(int x, int y, int z) {
  nex[++cntedge] = head[x];
  from[cntedge] = x;
  to[cntedge] = y;
  cap[cntedge] = z;
  flow[cntedge] = 0;
  head[x] = cntedge;
}
int cur[maxn];
int d[maxn];
int vis[maxn];
int q[maxn], r;
int Bfs() {
  for (int i = 1; i <= n; ++i) vis[i] = 0;
  vis[1] = 1;
  d[1] = 0;
  q[r = 1] = 1;
  for (int l = 1; l <= r; ++l) {
    int x = q[l];
    for (int i = head[x]; i; i = nex[i]) {
      int v = to[i];
      if ((cap[i] > flow[i]) && (!vis[v])) {
        vis[v] = 1;
        d[v] = d[x] + 1;
        q[++r] = v;
      }
    }
  }
  return vis[n];
}
int Dfs(int x, int a) {
  if ((x == n) || (a == 0)) return a;
  int nowflow = 0, f = 0;
  for (int i = cur[x]; i; i = nex[i]) {
    cur[x] = i;
    int v = to[i];
    if (d[x] + 1 == d[v]) {
      f = Dfs(v, min(a, cap[i] - flow[i]));
      nowflow += f;
      a -= f;
      flow[i] += f;
      flow[i ^ 1] -= f;
      if (a == 0) break;
    }
  }
  return nowflow;
}
int p[maxn], pf[maxn] = {0, 1000000};
int augment() {
  for (int i = 1; i <= n; ++i) vis[i] = 0;
  q[r = 1] = 1;
  int flag = 0;
  for (int l = 1; l <= r; ++l) {
    int x = q[l];
    for (int i = head[x]; i; i = nex[i]) {
      int v = to[i];
      if ((cap[i] > flow[i]) && (!vis[v])) {
        vis[v] = 1;
        p[v] = i;
        q[++r] = v;
        pf[v] = min(pf[x], cap[i] - flow[i]);
        if (v == n) {
          flag = 1;
          break;
        }
      }
    }
    if (flag) break;
  }
  if (!vis[n]) return 0;
  int f = pf[n], x = n;
  while (x != 1) {
    flow[p[x]] += f;
    flow[p[x] ^ 1] -= f;
    x = from[p[x]];
  }
  return f;
}
int Maxflow() {
  int flow = 0;
  while (Bfs()) {
    for (int i = 1; i <= n; ++i) cur[i] = head[i];
    flow += Dfs(1, inf);
  }
  return flow;
}
int f[1024];
int sum[1 << 10];
int lg2[1 << 11];
int w[maxn];
int read() {
  int r = 0, k = 1;
  char c = getchar();
  for (; c < '0' || c > '9'; c = getchar())
    if (c == '-') k = -1;
  for (; c >= '0' && c <= '9'; c = getchar()) r = r * 10 + c - '0';
  return r * k;
}
int main() {
  scanf("%d%d%d%d", &n, &m, &K, &T);
  for (int i = 1; i <= m; ++i) {
    int x, y, z;
    scanf("%d%d%d", &x, &y, &z);
    Addedge(x, y, z);
    Addedge(y, x, 0);
  }
  f[0] = Maxflow();
  for (int i = 2; i <= cntedge; ++i) e[0][i] = flow[i];
  for (int s = 1; s < (1 << K); ++s) {
    for (int i = 1; i <= K; ++i) {
      if (s & (1 << (i - 1))) {
        cap[i << 1] = 25;
      } else {
        cap[i << 1] = 0;
      }
    }
    int pre = s ^ (s & (-s));
    for (int i = 2; i <= cntedge; ++i) flow[i] = e[pre][i];
    f[s] = f[pre];
    int tmp;
    while (tmp = augment()) f[s] += tmp;
    for (int i = 2; i <= cntedge; ++i) e[s][i] = flow[i];
  }
  for (int s = 0; s < (1 << K); ++s) {
    int t = (~s) & ((1 << K) - 1);
    if (t < s) swap(f[s], f[t]);
  }
  for (int i = 1; i <= 10; ++i) lg2[1 << i] = i;
  while (T--) {
    for (int i = 1; i <= K; ++i) w[i] = read();
    int ans = f[0];
    for (int s = 1; s < (1 << K); ++s) {
      int l = s & (-s);
      sum[s] = sum[s ^ l] + w[lg2[l] + 1];
      ans = min(ans, sum[s] + f[s]);
    }
    printf("%d\n", ans);
  }
  return 0;
}
