import sys from collections import deque def main(): sys.setrecursionlimit(1 << 25) input = sys.stdin.read().split() idx = 0 N = int(input[idx]) idx +=1 M = int(input[idx]) idx +=1 A = [] B = [] C = [] for _ in range(N): a = int(input[idx]) b = int(input[idx+1]) c = int(input[idx+2]) A.append(a) B.append(b) C.append(c) idx +=3 # Preprocess each group's possible B candidates group_candidates = [[] for _ in range(N)] all_B = B.copy() M_i_list = [] for i in range(N): a = A[i] c = C[i] mi = max(a, c) min_ac = min(a, c) M_i_list.append(mi) for bj_idx in range(N): bj = all_B[bj_idx] if bj > mi: if bj != a and bj != c: group_candidates[i].append(bj_idx) else: if (a < c and bj < a) or (a > c and bj < c): if bj != a and bj != c: group_candidates[i].append(bj_idx) # Build bipartite graph for perfect matching check graph = [[] for _ in range(N)] for i in range(N): for bj_idx in group_candidates[i]: graph[i].append(bj_idx) # Hopcroft-Karp algorithm for bipartite matching def hopcroft_karp(): pair_U = [-1] * N pair_V = [-1] * N dist = [0] * N def bfs(): queue = deque() for u in range(N): if pair_U[u] == -1: dist[u] = 0 queue.append(u) else: dist[u] = float('inf') dist_null = float('inf') while queue: u = queue.popleft() if dist[u] < dist_null: for v in graph[u]: if pair_V[v] == -1: dist_null = dist[u] +1 elif dist[pair_V[v]] == float('inf'): dist[pair_V[v]] = dist[u] +1 queue.append(pair_V[v]) return dist_null != float('inf') def dfs(u): for v in graph[u]: if pair_V[v] == -1 or (dist[pair_V[v]] == dist[u]+1 and dfs(pair_V[v])): pair_U[u] = v pair_V[v] = u return True dist[u] = float('inf') return False result = 0 while bfs(): for u in range(N): if pair_U[u] == -1: if dfs(u): result +=1 return result == N if not hopcroft_karp(): print("NO") return # Now, calculate maximum possible sum sum_M = sum(M_i_list) extra_candidates = [] for i in range(N): a = A[i] c = C[i] mi = M_i_list[i] for bj_idx in group_candidates[i]: bj = all_B[bj_idx] if bj > mi: extra = bj - mi extra_candidates.append((-extra, i, bj_idx)) # use negative for min heap # Sort by descending extra extra_candidates.sort() group_used = [False] * N B_used = [False] * N total_extra = 0 for ec in extra_candidates: extra = -ec[0] i = ec[1] bj_idx = ec[2] if not group_used[i] and not B_used[bj_idx]: group_used[i] = True B_used[bj_idx] = True total_extra += extra total = sum_M + total_extra print("YES") if total >= M: print("KADOMATSU!") else: print("NO") if __name__ == "__main__": main()