// ---------- begin input macro ---------- // reference: https://qiita.com/tanakh/items/0ba42c7ca36cd29d0ac8 macro_rules! input { (source = $s:expr, $($r:tt)*) => { let mut iter = $s.split_whitespace(); input_inner!{iter, $($r)*} }; ($($r:tt)*) => { let s = { use std::io::Read; let mut s = String::new(); std::io::stdin().read_to_string(&mut s).unwrap(); s }; let mut iter = s.split_whitespace(); input_inner!{iter, $($r)*} }; } macro_rules! input_inner { ($iter:expr) => {}; ($iter:expr, ) => {}; ($iter:expr, $var:ident : $t:tt $($r:tt)*) => { let $var = read_value!($iter, $t); input_inner!{$iter $($r)*} }; } macro_rules! read_value { ($iter:expr, ( $($t:tt),* )) => { ( $(read_value!($iter, $t)),* ) }; ($iter:expr, [ $t:tt ; $len:expr ]) => { (0..$len).map(|_| read_value!($iter, $t)).collect::>() }; ($iter:expr, chars) => { read_value!($iter, String).chars().collect::>() }; ($iter:expr, bytes) => { read_value!($iter, String).bytes().collect::>() }; ($iter:expr, usize1) => { read_value!($iter, usize) - 1 }; ($iter:expr, $t:ty) => { $iter.next().unwrap().parse::<$t>().expect("Parse error") }; } // ---------- end input macro ---------- // bmax // bの昇順にマッチ可能なもの中でaが最小のやつをとるのがいい // bmin // bの降順にマッチ可能なものの中でaが最小のやつをとるといい // これはマッチングができるかの判定 // スコアを最大化するにはbmax でc が大きいやつを残したいという思想が出てくる // 落ち着くとbmin はaが最小じゃなくてもOK // bmin はマッチ可能なものの中でcが最大のものを撮るのが最適 fn run() { input! { n: usize, m: i64, p: [(i64, i64, i64); n], } let mut b = p.iter().map(|p| p.1).collect::>(); b.sort(); let p = p.into_iter().enumerate().map(|(k, p)| (p.0, p.2, k)).collect::>(); let mut ans: Option = None; for i in 0..=n { let (l, r) = b.split_at(i); let mut e = vec![]; for l in l.iter() { e.push((-*l, 0, 0)); } for &(a, _, k) in p.iter() { e.push((-a, 1, k)); } e.sort(); let mut h = std::collections::BinaryHeap::<(i64, usize)>::new(); let mut cnt = 0; let mut sum = 0; for (_, op, k) in e { if op == 0 { if let Some((c, _k)) = h.pop() { sum += c; cnt += 1; } } else { h.push((p[k].1, k)); } } let p = h.into_iter().map(|(_, k)| (p[k].0, p[k].1)).collect::>(); let mut e = vec![]; for r in r.iter() { e.push((*r, 0)); } for &(_, c) in p.iter() { e.push((c, 1)); } e.sort(); let mut stack = 0; for (c, op) in e { if op == 0 { if stack > 0 { cnt += 1; sum += c; stack -= 1; } } else { stack += 1; } } if cnt == n { if ans.is_none() { ans = Some(sum); } else { let v = ans.unwrap(); ans = Some(v.max(sum)); } } } if let Some(ans) = ans { println!("YES"); if ans >= m { println!("KADOMATSU!"); } else { println!("NO"); } } else { println!("NO"); } } fn main() { run(); }