import java.io.IOException; import java.io.InputStream; import java.util.Arrays; import java.util.Comparator; import java.util.HashMap; import java.util.NoSuchElementException; import java.util.PriorityQueue; class Main { public static void main(String[] args) { long curtime = System.currentTimeMillis(); new Main().run(); System.err.println(System.currentTimeMillis() - curtime); } long[] C; long[] sumC; final void run() { Scanner sc = new Scanner(); int N = sc.nextInt(); long M = sc.nextLong(); long[][] A = new long[N][2]; C = new long[N]; sumC = new long[N]; for (int i = 0; i < N; ++i) { A[i][0] = sc.nextInt(); C[i] = sc.nextInt(); A[i][1] = sc.nextInt(); } String[] ret = solve(N, M, A); for (String s : ret) { System.out.println(s); } } PriorityQueue pq = new PriorityQueue<>(new Comparator() { @Override public int compare(long[] o1, long[] o2) { if (o1[0] != o2[0]) return Long.compare(o1[0], o2[0]); else return Long.compare(o1[2], o2[2]); } }); final long check(long middle, int N, long M, long[][] A, boolean center) { if (!pq.isEmpty()) { throw new AssertionError(); } for (int i = 0; i < N; ++i) { long l = binarySearchLeft(A[i][0]); long r = binarySearchRight(A[i][1]); if (!center) { l = Math.min(l, middle); r = Math.max(r, middle + 1); } A[i] = new long[] { l, r, A[i][0], A[i][1] }; } Arrays.sort(A, new Comparator() { @Override public int compare(long[] o1, long[] o2) { return Long.compare(o1[0], o2[0]); } }); int p = 0, maxsz = 0; long ans = 0; Arrays.fill(need, 0); Arrays.fill(sz, 0); for (int i = -1; i <= N; ++i) { while (p < A.length && A[p][0] <= i) { pq.add(new long[] { A[p][1], A[p][2], A[p][3] }); ++p; maxsz = Math.max(maxsz, pq.size()); } while (pq.size() > i + 1) { long[] v = pq.poll(); if (v[0] >= N) { pq.clear(); return -1; } need[(int) v[0]]--; } if (0 <= i && i < sz.length) sz[i] = pq.size(); } for (int i = 1; i < N; ++i) { need[i] = need[i - 1] + need[i]; } boolean ok = true; int pnd = 0, cur = 0; for (int i = 0; i < N; ++i) { pnd += Math.abs(need[i]); if (pnd > 0) { ++cur; --pnd; } need[i] = (i + 1) - cur; } int max = 0; for (int i = N - 1; i >= 0; --i) { max = Math.max(max, sz[i]); ok &= max >= need[i]; } if (!ok) { pq.clear(); return -1; } ans += sumC[N - 1] - (pq.size() > 0 ? sumC[pq.size() - 1] : 0); if (center) { int ret = pq.size(); pq.clear(); return ret; } while (!pq.isEmpty()) { ans += pq.poll()[2]; } return ans; } final long[][] copy(long[][] A_) { for (int i = 0; i < A_.length; ++i) for (int j = 0; j < A_[i].length; ++j) A[i][j] = A_[i][j]; return A; } int[] need; int[] sz; long[][] A; final String[] solve(int N, long M, long[][] A_) { need = new int[N]; sz = new int[N]; A = new long[A_.length][A_[0].length]; for (int i = 0; i < A_.length; ++i) Arrays.sort(A_[i]); Arrays.sort(C); for (int i = 0; i < sumC.length; ++i) sumC[i] = (i > 0 ? sumC[i - 1] : 0) + C[i]; long ret = -1; long center = check(-1, N, M, copy(A_), true); if (center == -1) return new String[] { "NO" }; long left, right; if (check(-1, N, M, copy(A_), false) > 0) { left = -1; } else { long lng = -1; left = center; while (left - lng > 1) { long middle = (left + lng) / 2; if (check(middle, N, M, copy(A_), false) > 0) { left = middle; } else { lng = middle; } } } if (check(N, N, M, copy(A_), false) > 0) { right = N; } else { long rng = N; right = center; while (rng - right > 1) { long middle = (rng + right) / 2; if (check(middle, N, M, copy(A_), false) > 0) { right = middle; } else { rng = middle; } } } while (right - left > 2) { long lm = (right + 2 * left) / 3;// l+(r-l)/3=(r+2l)/3 long rm = (2 * right + left) / 3; long lmv = check(lm, N, M, copy(A_), false); long rmv = check(rm, N, M, copy(A_), false); if (lmv > rmv) right = rm; else left = lm; ret = Math.max(ret, lmv); ret = Math.max(ret, rmv); } for (long i = left; i <= right; ++i) ret = Math.max(ret, check(i, N, M, copy(A_), false)); if (ret >= M) return new String[] { "YES", "KADOMATSU!" }; else if (ret > 0) { return new String[] { "YES", "NO" }; } else { return new String[] { "NO" }; } } HashMap right = new HashMap<>(); final int binarySearchRight(long key) { if (right.containsKey(key)) return right.get(key); int ok = C.length; int ng = -1; while (ok - ng > 1) { int middle = (ok + ng) / 2; if (C[middle] > key) { ok = middle; } else { ng = middle; } } right.put(key, ok); return ok; } HashMap left = new HashMap<>(); final int binarySearchLeft(long key) { if (left.containsKey(key)) return left.get(key); int ok = -1; int ng = C.length; while (ng - ok > 1) { int middle = (ok + ng) / 2; if (C[middle] < key) { ok = middle; } else { ng = middle; } } left.put(key, ok); return ok; } void tr(Object... objects) { System.out.println(Arrays.deepToString(objects)); } } class Scanner { private final InputStream in = System.in; private final byte[] buffer = new byte[1024]; private int ptr = 0; private int buflen = 0; private boolean hasNextByte() { if (ptr < buflen) { return true; } else { ptr = 0; try { buflen = in.read(buffer); } catch (IOException e) { e.printStackTrace(); } if (buflen <= 0) { return false; } } return true; } private int readByte() { if (hasNextByte()) return buffer[ptr++]; else return -1; } private static boolean isPrintableChar(int c) { return 33 <= c && c <= 126; } private void skipUnprintable() { while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++; } public boolean hasNext() { skipUnprintable(); return hasNextByte(); } public String next() { if (!hasNext()) throw new NoSuchElementException(); StringBuilder sb = new StringBuilder(); int b = readByte(); while (isPrintableChar(b)) { sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } public int nextInt() { return (int) nextLong(); } public long nextLong() { if (!hasNext()) throw new NoSuchElementException(); long n = 0; boolean minus = false; int b = readByte(); if (b == '-') { minus = true; b = readByte(); } if (b < '0' || '9' < b) { throw new NumberFormatException(); } while (true) { if ('0' <= b && b <= '9') { n *= 10; n += b - '0'; } else if (b == -1 || !isPrintableChar(b)) { return minus ? -n : n; } else { throw new NumberFormatException(); } b = readByte(); } } }