#include using namespace std; using int64 = long long; const int mod = 1e9 + 7; //const int mod = 998244353; const int64 infll = (1LL << 62) - 1; const int inf = (1 << 30) - 1; struct IoSetup { IoSetup() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(10); cerr << fixed << setprecision(10); } } iosetup; template< typename T1, typename T2 > ostream &operator<<(ostream &os, const pair< T1, T2 > &p) { os << p.first << " " << p.second; return os; } template< typename T1, typename T2 > istream &operator>>(istream &is, pair< T1, T2 > &p) { is >> p.first >> p.second; return is; } template< typename T > ostream &operator<<(ostream &os, const vector< T > &v) { for(int i = 0; i < (int) v.size(); i++) { os << v[i] << (i + 1 != v.size() ? " " : ""); } return os; } template< typename T > istream &operator>>(istream &is, vector< T > &v) { for(T &in : v) is >> in; return is; } template< typename T1, typename T2 > inline bool chmax(T1 &a, T2 b) { return a < b && (a = b, true); } template< typename T1, typename T2 > inline bool chmin(T1 &a, T2 b) { return a > b && (a = b, true); } template< typename T = int64 > vector< T > make_v(size_t a) { return vector< T >(a); } template< typename T, typename... Ts > auto make_v(size_t a, Ts... ts) { return vector< decltype(make_v< T >(ts...)) >(a, make_v< T >(ts...)); } template< typename T, typename V > typename enable_if< is_class< T >::value == 0 >::type fill_v(T &t, const V &v) { t = v; } template< typename T, typename V > typename enable_if< is_class< T >::value != 0 >::type fill_v(T &t, const V &v) { for(auto &e : t) fill_v(e, v); } template< typename F > struct FixPoint : F { FixPoint(F &&f) : F(forward< F >(f)) {} template< typename... Args > decltype(auto) operator()(Args &&... args) const { return F::operator()(*this, forward< Args >(args)...); } }; template< typename F > inline decltype(auto) MFP(F &&f) { return FixPoint< F >{forward< F >(f)}; } template< typename key_t, typename val_t > struct RadixHeap { static constexpr int bit = sizeof(key_t) * 8; array< vector< pair< key_t, val_t > >, bit > vs; size_t sz; key_t last; RadixHeap() : sz(0), last(0) {} bool empty() const { return sz == 0; } size_t size() const { return sz; } inline int getbit(int a) const { return a ? bit - __builtin_clz(a) : 0; } inline int getbit(int64_t a) const { return a ? bit - __builtin_clzll(a) : 0; } void push(const key_t &key, const val_t &val) { sz++; vs[getbit(key ^ last)].emplace_back(key, val); } pair< key_t, val_t > pop() { if(vs[0].empty()) { int idx = 1; while(vs[idx].empty()) idx++; last = min_element(vs[idx].begin(), vs[idx].end())->first; for(auto &p:vs[idx]) vs[getbit(p.first ^ last)].emplace_back(p); vs[idx].clear(); } --sz; auto res = vs[0].back(); vs[0].pop_back(); return res; } }; //BEGIN CUT HERE // O(m^2 \log m \log U) // U: maximum capacity enum Objective { MINIMIZE = +1, MAXIMIZE = -1, }; template< typename Flow, typename Cost, Objective objective = Objective::MINIMIZE > struct MinCostFlow { template< typename T > inline void chmin(T &x, T y) { x = min(x, y); } struct Edge { int src, dst; Flow flow, cap; Cost cost; int rev; Edge(int src, int dst, Flow cap, Cost cost, int rev) : src(src), dst(dst), flow(0), cap(cap), cost(cost), rev(rev) {} Flow residual_cap() const { return cap - flow; } }; struct EdgePtr { int v, e; EdgePtr(int v, int e) : v(v), e(e) {} }; int n; vector< vector< Edge>> G; vector< Flow > b; vector< Cost > p; MinCostFlow(int n) : n(n), G(n), b(n, 0) {} EdgePtr add_edge(int src, int dst, Flow lower, Flow upper, Cost cost) { int e = G[src].size(); int r = (src == dst ? e + 1 : G[dst].size()); assert(lower <= upper); G[src].emplace_back(src, dst, +upper, +cost * objective, r); G[dst].emplace_back(dst, src, -lower, -cost * objective, e); return EdgePtr(src, e); } const Edge &get_edge(EdgePtr ep) const { return G[ep.v][ep.e]; } void push(Edge &e, Flow amount) { e.flow += amount; G[e.dst][e.rev].flow -= amount; } void add_supply(int v, Flow amount) { b[v] += amount; } void add_demand(int v, Flow amount) { b[v] -= amount; } Cost residual_cost(const Edge &e) { return e.cost + p[e.src] - p[e.dst]; } vector< int > excess_vs, deficit_vs; void saturate_negative(const Flow delta) { for(auto &es:G) { for(auto &e:es) { Flow cap = e.residual_cap(); cap -= cap % delta; if(cap < 0 or residual_cost(e) < 0) { push(e, cap); b[e.src] -= cap; b[e.dst] += cap; } } } excess_vs.clear(); deficit_vs.clear(); for(int v = 0; v < n; v++) { if(b[v] > 0) excess_vs.emplace_back(v); if(b[v] < 0) deficit_vs.emplace_back(v); } } const Cost unreachable = std::numeric_limits< Cost >::max(); Cost farthest; vector< Cost > dist; vector< Edge * > parent; struct P { Cost first; int second; P(Cost first, int second) : first(first), second(second) {} bool operator<(const P o) const { return first > o.first; } }; priority_queue< P > pq; template< typename Predicate > void eliminate(vector< int > &vs, Predicate predicate) { vs.erase(remove_if(begin(vs), end(vs), predicate), end(vs)); } bool dual(const Flow delta) { eliminate(excess_vs, [&](int v) { return b[v] < +delta; }); eliminate(deficit_vs, [&](int v) { return b[v] > -delta; }); dist.assign(n, unreachable); for(int v:excess_vs) pq.emplace(dist[v] = 0, v); parent.assign(n, nullptr); auto emplace = [&](Edge &e) { if(e.residual_cap() < delta) return; Cost nxt = dist[e.src] + residual_cost(e); if(nxt >= dist[e.dst]) return; pq.emplace(dist[e.dst] = nxt, e.dst); parent[e.dst] = &e; }; farthest = 0; int deficit_count = 0; while(!pq.empty()) { Cost d = pq.top().first; int v = pq.top().second; pq.pop(); if(dist[v] < d) continue; farthest = d; if(b[v] <= -delta) deficit_count++; if(deficit_count >= (int) deficit_vs.size()) break; for(auto &e:G[v]) emplace(e); } pq = decltype(pq)(); for(int v = 0; v < n; v++) p[v] += min(dist[v], farthest); return deficit_count > 0; } void primal(const Flow delta) { for(int t:deficit_vs) { if(dist[t] > farthest) continue; Flow f = -b[t]; int v; for(v = t; parent[v]; v = parent[v]->src) chmin(f, parent[v]->residual_cap()); chmin(f, b[v]); f -= f % delta; if(f <= 0) continue; for(v = t; parent[v];) { auto &e = *parent[v]; push(e, f); int u = parent[v]->src; if(e.residual_cap() <= 0) parent[v] = nullptr; v = u; } b[t] += f; b[v] -= f; } } template< Flow SCALING_FACTOR = 2 > bool build() { p.resize(n); Flow max_flow = 1; for(auto t:b) max_flow = max({max_flow, t, -t}); for(auto &es:G) for(auto &e:es) max_flow = max({max_flow, e.residual_cap(), -e.residual_cap()}); Flow delta = 1; while(delta < max_flow) delta *= SCALING_FACTOR; for(; delta; delta /= SCALING_FACTOR) { saturate_negative(delta); while(dual(delta)) primal(delta); } return excess_vs.empty() and deficit_vs.empty(); } template< typename T=Cost > T get_cost() { T res = 0; for(auto &es:G) for(auto &e:es) res += T(e.flow) * T(e.cost) / T(objective); return res / T(2); } template< typename T=Cost > T get_gain() { return get_cost(); } vector< Cost > get_potential() { fill(p.begin(), p.end(), 0); for(int i = 0; i < n; i++) for(auto &es:G) for(auto &e:es) if(e.residual_cap() > 0) chmin(p[e.dst], p[e.src] + e.cost); return p; } }; template< typename Flow, typename Cost > using MaxGainFlow = MinCostFlow< Flow, Cost, Objective::MAXIMIZE >; template< typename Flow, typename Cost > using MinGainFlow = MinCostFlow< Flow, Cost, Objective::MINIMIZE >; int main() { int N; int64 M; cin >> N >> M; vector< int > X(N), Y(N), Z(N); for(int i = 0; i < N; i++) { int A, B, C; cin >> A >> B >> C; if(A > C) swap(A, C); X[i] = A; Y[i] = B; Z[i] = C; } sort(begin(Y), end(Y)); MinGainFlow< int, int64 > flow(N + N + N + N + 2); int S = N + N + N + N; int T = S + 1; // <----- for(int i = N - 2; i >= 0; i--) { flow.add_edge(i + N + 1, i + N, 0, N, 0); } // ----> for(int i = 1; i < N; i++) { flow.add_edge(i + N + N - 1, i + N + N, 0, N, 0); } for(int i = 0; i < N; i++) { flow.add_edge(i + N, i + N + N + N, 0, 1, 0); flow.add_edge(i + N + N, i + N + N + N, 0, 1, inf - Y[i]); flow.add_edge(i + N + N + N, T, 0, 1, 0); } for(int i = 0; i < N; i++) { vector< int > ok(N); for(int j = 0; j < N; j++) { if(Y[j] < X[i]) ok[j] = 1; else if(Z[i] < Y[j]) ok[j] = 2; } flow.add_edge(S, i, 0, 1, 0); for(int j = 0; j < N; j++) { if(ok[j] == 2) { flow.add_edge(i, j + N + N, 0, 1, 0); break; } } for(int j = N - 1; j >= 0; j--) { if(ok[j] == 1) { flow.add_edge(i, j + N, 0, 1, inf - Z[i]); break; } } } flow.add_supply(S, N); flow.add_demand(T, N); if(!flow.build()) { cout << "NO\n"; } else { cout << "YES\n"; auto ret = flow.get_cost(); ret -= 1LL * inf * N; ret *= -1; if(ret >= M) cout << "KADOMATSU!\n"; else cout << "NO\n"; } }