// 最短路反復法 // src -> dst へflowだけ流せた時コストを返す // 負閉路はないと仮定 const INF: i64 = 1_000_000_000_000_000i64 + 1; struct Graph { size: usize, edge: Vec<(usize, usize, i64, i64)>, } impl Graph { fn new(size: usize) -> Self { Graph { size: size, edge: vec![], } } fn add_edge(&mut self, src: usize, dst: usize, capa: i64, cost: i64) { assert!(src < self.size && dst < self.size && src != dst); self.edge.push((src, dst, capa, cost)); } fn flow(&self, src: usize, dst: usize, flow: i64) -> Result { if src == dst { return Ok(0); } let size = self.size; let edge = &self.edge; let mut deg = vec![0; size]; for &(a, b, _, _) in edge.iter() { deg[a] += 1; deg[b] += 1; } let mut graph: Vec<_> = deg.into_iter().map(|d| Vec::with_capacity(d)).collect(); for &(a, b, capa, cost) in edge.iter() { let x = graph[a].len(); let y = graph[b].len(); graph[a].push((b, capa, cost, y)); graph[b].push((a, 0, -cost, x)); } let mut ans = 0; let mut rem = flow; let mut dp = Vec::with_capacity(size); let mut pot = vec![0; size]; let mut h = std::collections::BinaryHeap::new(); while rem > 0 { dp.clear(); dp.resize(size, (INF, src, 0));// コスト、親、親からの番号 dp[src] = (0, src, 0); h.push((0, src)); while let Some((d, v)) = h.pop() { let d = -d; if d > dp[v].0 { continue; } for (i, &(u, capa, cost, _)) in graph[v].iter().enumerate() { if capa == 0 { continue; } let c = d + cost - pot[u] + pot[v]; if c < dp[u].0 { dp[u] = (c, v, i); h.push((-c, u)); } } } if dp[dst].0 == INF { return Err((flow - rem, ans)); } for i in 0..size { pot[i] -= dp[dst].0 - dp[i].0; } let mut sub = rem; let mut pos = dst; while pos != src { let (_, parent, k) = dp[pos]; sub = sub.min(graph[parent][k].1); pos = parent; } let mut pos = dst; while pos != src { let (_, parent, k) = dp[pos]; let inv = graph[parent][k].3; graph[parent][k].1 -= sub; graph[pos][inv].1 += sub; pos = parent; } rem -= sub; ans += -pot[src] * sub; } Ok(ans) } } // ---------- 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 ---------- 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 mut p = p.iter().enumerate().map(|(k, p)| (p.0.min(p.2), p.0.max(p.2), k)).collect::>(); let mut g = Graph::new(4 * n + 2); let src = 4 * n; let dst = src + 1; let geta = 1_000_000_000; for i in 0..n { g.add_edge(src, i, 1, 0); } p.sort_by_key(|p| p.1); for i in 1..n { g.add_edge(n + p[i].2, n + p[i - 1].2, 3000, 0); } let mut x = n; for &(_a, c, k) in p.iter().rev() { g.add_edge(n + k, 2 * n + k, 1, 0); while x > 0 && b[x - 1] > c { x -= 1; g.add_edge(x, n + k, 1, geta - b[x]); } } p.sort_by_key(|p| p.0); for i in 0..(n - 1) { g.add_edge(3 * n + p[i].2, 3 * n + p[i + 1].2, 3000, 0); } let mut x = 0; for &(a, c, k) in p.iter() { g.add_edge(3 * n + k, 2 * n + k, 1, geta - c); while x < n && b[x] < a { g.add_edge(x, 3 * n + k, 1, 0); x += 1; } } for i in 0..n { g.add_edge(2 * n + i, dst, 1, 0); } if let Ok(ans) = g.flow(src, dst, n as i64) { println!("YES"); if n as i64 * geta - ans >= m { println!("KADOMATSU!"); } else { println!("NO"); } } else { println!("NO"); } } fn main() { run(); }