#include <bits/stdc++.h>
using namespace std;
const int N = 1e4 + 6;
const int M = 2e4 + 6;
int n, m, k, Q;
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch > '9' || ch < '0') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
struct edge {
  int to, next, f;
} e[M];
int tot, head[N];
void add(int x, int y, int v) {
  e[++tot] = (edge){y, head[x], v};
  head[x] = tot;
  e[++tot] = (edge){x, head[y], 0};
  head[y] = tot;
}
int visT;
int vis[N], q[N], dis[N], cur[N];
bool bfs() {
  int h = 0, t = 1;
  vis[1] = ++visT;
  q[1] = 1;
  dis[1] = 0;
  cur[1] = head[1];
  while (h != t) {
    int x = q[++h];
    for (int i = head[x]; i; i = e[i].next)
      if (vis[e[i].to] != visT && e[i].f) {
        dis[e[i].to] = dis[x] + 1;
        vis[e[i].to] = visT;
        cur[e[i].to] = head[e[i].to];
        if (e[i].to == n) return 1;
        q[++t] = e[i].to;
      }
  }
  return 0;
}
int C(int i) {
  if (i % 2)
    return i + 1;
  else
    return i - 1;
}
int dfs(int x, int flow) {
  if (x == n) return flow;
  int k, rest = flow;
  for (int &i = cur[x]; i && rest; i = e[i].next)
    if (dis[e[i].to] == dis[x] + 1 && vis[e[i].to] == visT && e[i].f) {
      k = dfs(e[i].to, min(e[i].f, flow));
      e[i].f -= k;
      e[C(i)].f += k;
      rest -= k;
      if (!rest) break;
    }
  if (rest) dis[x] = -1;
  return flow - rest;
}
int dinic() {
  int ans = 0;
  for (; bfs(); ans += dfs(1, 1 << 20))
    ;
  return ans;
}
int f[1200];
int temp[12][M];
int bfss() {
  int h = 0, t = 1;
  vis[1] = ++visT;
  q[1] = 1;
  cur[1] = 0;
  while (h != t) {
    int x = q[++h];
    for (int i = head[x]; i; i = e[i].next)
      if (vis[e[i].to] != visT && e[i].f) {
        vis[e[i].to] = visT;
        cur[e[i].to] = i;
        if (e[i].to == n) {
          int mn = 1 << 30;
          for (int j = cur[n]; j; j = cur[e[C(j)].to]) mn = min(mn, e[j].f);
          for (int j = cur[n]; j; j = cur[e[C(j)].to])
            e[j].f -= mn, e[C(j)].f += mn;
          return mn;
        }
        q[++t] = e[i].to;
      }
  }
  return 0;
}
int id[N];
void work(int d, int s, int p) {
  if (d == k + 1) {
    f[s] = p;
    return;
  }
  int node = id[d];
  work(d + 1, s, p);
  for (int i = 1; i <= tot; i++) temp[d][i] = e[i].f;
  e[node * 2 - 1].f += 25;
  int v = 0;
  for (int val; val = bfss(); v += val)
    ;
  work(d + 1, s | (1 << (node - 1)), p + v);
  for (int i = 1; i <= tot; i++) e[i].f = temp[d][i];
}
int w[15];
int sum[1200];
int main() {
  scanf("%d %d %d %d", &n, &m, &k, &Q);
  for (int i = 1; i <= m; i++) {
    int u, v, w;
    scanf("%d %d %d", &u, &v, &w);
    add(u, v, w);
  }
  f[0] = dinic();
  for (int i = 1; i <= k; i++) id[i] = i;
  random_shuffle(id + 1, id + k + 1);
  work(1, 0, f[0]);
  while (Q--) {
    for (int i = 1; i <= k; i++) scanf("%d", &w[i]);
    memset(sum, 0, sizeof(sum));
    for (int i = 1; i <= k; i++) sum[1 << (i - 1)] = w[i];
    int maxn = (1 << k);
    for (int j = 1; j < maxn; j++) sum[j] = sum[j - (j & (-j))] + sum[j & (-j)];
    int ans = 1e9;
    for (int j = 0; j < maxn; j++) ans = min(ans, f[j] + sum[maxn - 1 - j]);
    printf("%d\n", ans);
  }
}
