#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #define rep(x, s, t) for(llint (x) = (s); (x) <= (t); (x)++) #define chmin(x, y) (x) = min((x), (y)) #define chmax(x, y) (x) = max((x), (y)) #define all(x) (x).begin(),(x).end() #define inf 1e18 using namespace std; typedef long long llint; typedef long long ll; typedef pair P; struct MinCostFlow{ struct edge{ llint to, cap, cost, rev; edge(){} edge(llint a, llint b, llint c, llint d){ to = a, cap = b, cost = c, rev = d; } }; int n; vector > G; vector dist; vector prevv, preve; vector h; MinCostFlow(){} MinCostFlow(int n){ this->n = n; G.resize(n+1); dist.resize(n+1); prevv.resize(n+1); preve.resize(n+1); h.resize(n+1); } void BellmanFord(int s) { for(int i = 0; i <= n; i++) dist[i] = inf; dist[s] = 0, prevv[s] = -1; bool update = true; while(update){ update = false; for(int i = 0; i <= n; i++){ for(int j = 0; j < G[i].size(); j++){ if(G[i][j].cap == 0) continue; if(dist[G[i][j].to] > dist[i] + G[i][j].cost){ dist[G[i][j].to] = dist[i] + G[i][j].cost; prevv[G[i][j].to] = i; preve[G[i][j].to] = j; update = true; } } } } } void Dijkstra(int s) { for(int i = 0; i <= n; i++) dist[i] = inf; dist[s] = 0, prevv[s] = -1; priority_queue< P, vector

, greater

> Q; Q.push( make_pair(0, s) ); llint v, d; while(Q.size()){ d = Q.top().first; v = Q.top().second; Q.pop(); if(dist[v] < d) continue; for(int i = 0; i < G[v].size(); i++){ if(G[v][i].cap == 0) continue; llint u = G[v][i].to, c = h[v] - h[u] + G[v][i].cost; if(dist[u] > d + c){ dist[u] = d + c; prevv[u] = v; preve[u] = i; Q.push( P(dist[u], u) ); } } } } void add_edge(int from, int to, llint cap, llint cost) { G[from].push_back( edge(to, cap, cost, G[to].size()) ); G[to].push_back( edge(from, 0, -cost, G[from].size()-1) ); } llint calc(int s, int t, llint f, bool &flag) { BellmanFord(s); for(int i = 0; i <= n; i++) h[i] = dist[i]; llint ret = 0; while(f > 0){ Dijkstra(s); if(dist[t] >= inf) break; llint p = t, flow = f; while(prevv[p] != -1){ flow = min(flow, G[prevv[p]][preve[p]].cap); p = prevv[p]; } p = t; while(prevv[p] != -1){ G[prevv[p]][preve[p]].cap -= flow; G[p][G[prevv[p]][preve[p]].rev].cap += flow; p = prevv[p]; } f -= flow; ret += (dist[t] + h[t] - h[s]) * flow; for(int i = 0; i <= n; i++) h[i] += dist[i]; //オーバーフローに注意(?) } if(f > 0) flag = true; return ret; } }; ll n, m; ll l[3005], r[3005], a[3005]; MinCostFlow mcf(6005); int main(void) { ios::sync_with_stdio(0); cin.tie(0); cin >> n >> m; rep(i, 1, n){ cin >> l[i] >> a[i] >> r[i]; if(l[i] > r[i]) swap(l[i], r[i]); } rep(i, 1, n){ rep(j, 1, n){ if(r[i] < a[j]) mcf.add_edge(i, n+j, 1, -a[j]); if(l[i] > a[j]) mcf.add_edge(i, n+j, 1, -r[i]); } } ll S = 2*n+1, T = 2*n+2; rep(i, 1, n) mcf.add_edge(S, i, 1, 0), mcf.add_edge(n+i, T, 1, 0); bool flag = false; ll res = -mcf.calc(S, T, n, flag); if(flag) cout << "NO" << endl; else{ cout << "YES" << endl; if(res >= m) cout << "KADOMATSU!" << endl; else cout << "NO" << endl; } return 0; }