from collections import deque class mf_graph: def __init__(self, N) : self.size = N self.g = [[] for i in range(self.size)] self.gsz = [0 for i in range(self.size)] def add_edge(self, u, v, c) : self.g[u].append((v, len(self.g[v]), c)) self.g[v].append((u, len(self.g[u]) - 1, 0)) def Bfs(self, s, t) : q = [] self.went[s] = t self.Iter[s] = self.dep[s] = 0 q.append(s) while len(q) : now = q.pop() for i in self.g[now] : if i[2] > 0 and self.went[i[0]] != t : self.went[i[0]] = t self.dep[i[0]] = self.dep[now] + 1 self.Iter[i[0]] = 0 q.append(i[0]) def Dfs(self, u, t, nv) : if u == t : return nv while self.Iter[u] < self.gsz[u] : i = self.Iter[u] if self.g[u][i][2] > 0 and self.dep[self.g[u][i][0]] > self.dep[u] : if self.Dfs(self.g[u][i][0], t, nv) > 0 : self.g[u][i] = (self.g[u][i][0], self.g[u][i][1], 0) self.g[self.g[u][i][0]][self.g[u][i][1]] = (self.g[self.g[u][i][0]][self.g[u][i][1]][0], self.g[self.g[u][i][0]][self.g[u][i][1]][1], 1) return 1 self.Iter[u] += 1 return 0 def flow(self, s, t) : self.dep = [0 for i in range(self.size)] self.went = [0 for i in range(self.size)] self.Iter = [0 for i in range(self.size)] self.gsz = [len(self.g[i]) for i in range(self.size)] cnt = self.went[s] ans = 0; kInf = 1 << 30 while True : cnt += 1 self.Bfs(s, cnt) if self.went[s] != self.went[t] : break f = 0 while True : f = self.Dfs(s, t, kInf) if f > 0 : ans += f else : break return ans n, m, k, l = map(int, input().split()) x = [0] * l; y = [0] * l; z = [0] * l for i in range(l) : x[i], y[i], z[i] = map(int, input().split()) edges = [[] for i in range(k + 1)] for i in range(l) : edges[z[i]].append(i) alivex = [True] * (n + 1) alivey = [True] * (m + 1) wentx = [False] * (n + 1) wenty = [False] * (m + 1) val = [0] * (k + 1) matchx = [0] * (n + 1) matchy = [0] * (m + 1) S = 0; T = n + m + 1 G = mf_graph(n + m + 2) for j in range(1, n + 1) : G.add_edge(S, j, 1) for j in range(1, m + 1) : G.add_edge(j + n, T, 1) previous_edges = [] for i in range(k, -1, -1) : for j in edges[i] : if alivex[x[j]] and alivey[y[j]] : previous_edges.append(j) G.add_edge(x[j], y[j] + n, 1) gx = [[] for j in range(n + 1)] gy = [[] for j in range(m + 1)] for j in previous_edges : gx[x[j]].append(y[j]) gy[y[j]].append(x[j]) val[i] = G.flow(S, T) for j in range(1, n + 1) : matchx[j] = -1 for j in range(1, m + 1) : matchy[j] = -1 for j in range(1, n + 1) : wentx[j] = False for j in range(1, m + 1) : wenty[j] = False for j in range(1, n + 1) : for e in G.g[j] : if e[0] != S and e[2] == 0 and G.g[e[0]][e[1]][2] == 1 : matchx[j] = e[0] - n matchy[e[0] - n] = j qu = [] for j in range(1, n + 1) : if matchx[j] < 0 : wentx[j] = True qu.append(j) while len(qu) : idx = qu.pop() for j in gx[idx] : if not wentx[matchy[j]] : wentx[matchy[j]] = True qu.append(matchy[j]) for j in range(1, n + 1) : if not wentx[j] : alivex[j] = False for j in range(1, m + 1) : if matchy[j] < 0 : wenty[j] = True qu.append(j) while len(qu) : idx = qu.pop() for j in gy[idx] : if not wenty[matchx[j]] : wenty[matchx[j]] = True qu.append(matchx[j]) for j in range(1, m + 1) : if not wenty[j] : alivey[j] = False for j in range(1, n + 1) : if not wentx[j] : for idx in range(G.gsz[j]) : e = G.g[j][idx] if e[2] >= 0 and e[0] != S and not wenty[e[0] - n] and matchx[j] != e[0] - n : G.g[j][idx] = (G.g[j][idx][0], G.g[j][idx][1], 0) G.g[e[0]][e[1]] = (G.g[e[0]][e[1]][0], G.g[e[0]][e[1]][1], 0) psz = len(previous_edges) j = 0 while j < psz : idx = previous_edges[j] if not wentx[x[idx]] and not wenty[y[idx]] and matchx[x[idx]] != y[idx] : psz -= 1 previous_edges[j], previous_edges[psz] = previous_edges[psz], previous_edges[j] previous_edges.pop() j -= 1 j += 1 ans = 0 for i in range(0, k + 1) : ans += val[i] << i print(ans)