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) : self.g[u].append([v, self.gsz[v], 1]) self.g[v].append([u, self.gsz[u], 0]) self.gsz[u] += 1 self.gsz[v] += 1 def Bfs(self, s, t) : q = [s] idx = 0 q_sz = 1 self.went[s] = t self.Iter[s] = self.dep[s] = 0 while idx < q_sz : now = q[idx] idx += 1 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_sz += 1 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][2] = 0 self.g[self.g[u][i][0]][self.g[u][i][1]][2] = 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)] cnt = 0; 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 for i in range(n + 1)] alivey = [True for i in range(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) for j in range(1, m + 1) : G.add_edge(j + n, T) previous_edges = [] qu = [] qu_sz = 0 ans = 0 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) 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]) ans += G.flow(S, T) << i wentx = [False for i in range(n + 1)] wenty = [False for i in range(m + 1)] matchx = [-1 for i in range(n + 1)] matchy = [-1 for i in range(m + 1)] 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 for j in range(1, n + 1) : if matchx[j] < 0 : wentx[j] = True qu_sz += 1 qu.append(j) while qu_sz > 0 : idx = qu.pop() qu_sz -= 1 for j in gx[idx] : if not wentx[matchy[j]] : wentx[matchy[j]] = True qu_sz += 1 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_sz += 1 qu.append(j) while qu_sz > 0 : idx = qu.pop() qu_sz -= 1 for j in gy[idx] : if not wenty[matchx[j]] : wenty[matchx[j]] = True qu_sz += 1 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][2] = 0 G.g[e[0]][e[1]][2] = 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 print(ans)