#include <bits/stdc++.h>
using namespace std;
long long read() {
  long long x = 0, f = 0;
  char ch = getchar();
  while (!isdigit(ch)) f = ch == '-', ch = getchar();
  while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 48), ch = getchar();
  return f ? -x : x;
}
template <class T>
void ckmax(T &x, const T &y) {
  if (x < y) x = y;
}
template <class T>
void ckmin(T &x, const T &y) {
  if (x > y) x = y;
}
long long absl(long long x) { return x < 0 ? -x : x; }
const int N = 10005, M = N * 2, INF = 1e8;
struct Edge {
  int x, y, cap, nxt;
} e[M];
int cnt = 1;
int cur[N], dis[N], fst[N];
int q[N], head, tail;
int las[N], eid[N];
struct Graph {
  int n, s, t, flow;
  int cap[M];
  void init(int _n, int _s, int _t) {
    n = _n, s = _s, t = _t;
    cnt = 1, flow = 0;
  }
  void AddEdge(int x, int y, int _cap) {
    e[++cnt] = {x, y, 0, fst[x]}, cap[cnt] = _cap, fst[x] = cnt;
    e[++cnt] = {y, x, 0, fst[y]}, cap[cnt] = 0, fst[y] = cnt;
  }
  int bfs() {
    for (int i = (1); i <= (n); i++) dis[i] = INF;
    dis[t] = 0;
    head = 1, tail = 0;
    q[++tail] = t;
    while (head <= tail) {
      int x = q[head++];
      for (int i = fst[x]; i; i = e[i].nxt)
        if (cap[i ^ 1] && dis[e[i].y] == INF) {
          dis[e[i].y] = dis[x] + 1;
          q[++tail] = e[i].y;
        }
    }
    return dis[s] != INF;
  }
  int bfs2() {
    for (int i = (1); i <= (n); i++) dis[i] = INF;
    dis[t] = 0;
    head = 1, tail = 0;
    q[++tail] = t;
    while (head <= tail) {
      int x = q[head++];
      for (int i = fst[x]; i; i = e[i].nxt)
        if (cap[i ^ 1] && dis[e[i].y] == INF) {
          dis[e[i].y] = dis[x] + 1;
          las[e[i].y] = x;
          eid[e[i].y] = i ^ 1;
          q[++tail] = e[i].y;
          if (e[i].y == s) return 1;
        }
    }
    return dis[s] != INF;
  }
  int dfs(int x, int lim) {
    if (!lim || x == t) return lim;
    int rem = lim;
    for (int &i = cur[x]; i; i = e[i].nxt)
      if (cap[i] && dis[x] == dis[e[i].y] + 1) {
        int d = dfs(e[i].y, min(cap[i], rem));
        rem -= d;
        cap[i] -= d, cap[i ^ 1] += d;
        if (!rem) break;
      }
    return lim - rem;
  }
  int Dinic() {
    while (bfs()) {
      for (int i = (1); i <= (n); i++) cur[i] = fst[i];
      flow += dfs(s, INF);
    }
    return flow;
  }
  int Anti_Hack() {
    while (bfs2()) {
      int mx = 1e5;
      for (int i = s; i != t; i = las[i]) ckmin(mx, cap[eid[i]]);
      for (int i = s; i != t; i = las[i])
        cap[eid[i]] -= mx, cap[eid[i] ^ 1] += mx;
      flow += mx;
    }
    return flow;
  }
} g;
const int K = 10;
int n, m, k, Q;
int lg[1 << K], cost[1 << K];
vector<int> id;
int bakg[K][M];
void dfs(int t, int s) {
  if (t == k) {
    cost[s] = g.flow;
    return;
  }
  dfs(t + 1, s);
  for (int i = (2); i <= (cnt); i++) bakg[t][i] = g.cap[i];
  int fl = g.flow;
  g.cap[(id[t] + 1) * 2] = 25;
  g.Anti_Hack();
  dfs(t + 1, s | 1 << t);
  for (int i = (2); i <= (cnt); i++) g.cap[i] = bakg[t][i];
  g.flow = fl;
}
int sum[1 << K];
int main() {
  n = read(), m = read(), k = read(), Q = read();
  g.init(n, 1, n);
  for (int i = (0); i <= (m - 1); i++) {
    int x = read(), y = read(), cap = read();
    g.AddEdge(x, y, cap);
  }
  id.resize(k);
  iota(id.begin(), id.end(), 0);
  srand(time(0));
  random_shuffle(id.begin(), id.end());
  g.Dinic();
  dfs(0, 0);
  for (int i = (2); i <= ((1 << k) - 1); i++) lg[i] = lg[i >> 1] + 1;
  while (Q--) {
    vector<int> w(k);
    for (int i = (0); i <= (k - 1); i++) w[i] = read();
    int ans = INF;
    for (int i = (1); i <= ((1 << k) - 1); i++)
      sum[i] = sum[i - (1 << lg[i])] + w[id[lg[i]]];
    for (int i = (0); i <= ((1 << k) - 1); i++)
      ckmin(ans, sum[i] + cost[((1 << k) - 1) ^ i]);
    printf("%d\n", ans);
  }
  return 0;
}
