#[allow(unused_imports)] use std::cmp::{max, min, Ordering}; #[allow(unused_imports)] use std::collections::{HashMap, HashSet, BTreeSet}; mod util { use std::io::stdin; use std::str::FromStr; use std::fmt::Debug; #[allow(dead_code)] pub fn line() -> String { let mut line: String = String::new(); stdin().read_line(&mut line).unwrap(); line.trim().to_string() } #[allow(dead_code)] pub fn get() -> T where ::Err: Debug, { let mut line: String = String::new(); stdin().read_line(&mut line).unwrap(); line.trim().parse().unwrap() } #[allow(dead_code)] pub fn gets() -> Vec where ::Err: Debug, { let mut line: String = String::new(); stdin().read_line(&mut line).unwrap(); line.split_whitespace() .map(|t| t.parse().unwrap()) .collect() } #[allow(dead_code)] pub fn get2() -> (T, U) where ::Err: Debug, ::Err: Debug, { let mut line: String = String::new(); stdin().read_line(&mut line).unwrap(); let mut iter = line.split_whitespace(); ( iter.next().unwrap().parse().unwrap(), iter.next().unwrap().parse().unwrap(), ) } #[allow(dead_code)] pub fn get3() -> (S, T, U) where ::Err: Debug, ::Err: Debug, ::Err: Debug, { let mut line: String = String::new(); stdin().read_line(&mut line).unwrap(); let mut iter = line.split_whitespace(); ( iter.next().unwrap().parse().unwrap(), iter.next().unwrap().parse().unwrap(), iter.next().unwrap().parse().unwrap(), ) } } #[allow(unused_macros)] macro_rules! debug { ($x: expr) => { println!("{}: {:?}", stringify!($x), $x) } } #[derive(Clone)] struct BIT { buf: Vec, zero: T, } impl> BIT { fn new(n: usize, zero: &T) -> BIT { BIT { buf: vec![zero.clone(); n + 1], zero: zero.clone(), } } fn sum(&self, i: usize) -> T { let mut i = i; let mut s = self.zero.clone(); while i > 0 { s = s + self.buf[i].clone(); i = i & (i - 1); } s } fn add(&mut self, i: usize, x: &T) { let mut i = i as i64; while i < self.buf.len() as i64 { let y = { let t = self.buf[i as usize].clone(); t + x.clone() }; self.buf[i as usize] = y; i += i & -i; } } fn bin_search(&self, x: &T, low: usize, high: usize) -> usize { let mid = (low + high) / 2; if mid == low { return mid; } match self.sum(mid).cmp(x) { Ordering::Less => self.bin_search(x, mid, high), Ordering::Equal => self.bin_search(x, low, mid), Ordering::Greater => self.bin_search(x, low, mid), } } } fn main() { let (n, m): (usize, usize) = util::get2(); let inf = 100010; let xab: Vec<(usize, usize, usize)> = (0..n) .map(|_| { let (x, a, b): (usize, usize, usize) = util::get3(); (x, 100001 - a, 100001 - b) }) .collect(); let mut below_3 = vec![BIT::new(inf + 10, &0i64); 3]; let mut three = xab.iter().filter(|t| t.0 >= 3).count(); let av: BTreeSet = xab.iter().map(|t| t.1).collect(); let mut a_map = vec![Vec::new(); inf + 1]; let mut ans = inf; for &(x, a, b) in &xab { if x < 3 { below_3[x].add(b, &1); a_map[a].push((x, b)); } } // SA == inf { let two = three + below_3[2].sum(inf) as usize; if m > two { let rest = m - two; let sb = below_3[1].bin_search(&(rest as i64), 0, inf); if sb != inf { ans = min(ans, three + below_3[2].sum(sb) as usize); } } else { ans = min(ans, three); } } debug!(ans); for &a in &av { for &(x, b) in &a_map[a] { below_3[x].add(b, &-1); if x == 2 { three += 1; } else { below_3[x + 1].add(b, &1); } } let two = three + below_3[2].sum(inf) as usize; if m > two { let rest = m - two; let sb = below_3[1].bin_search(&(rest as i64), 0, inf); if sb != inf { ans = min(ans, three + below_3[2].sum(sb) as usize); } } else { ans = min(ans, three); debug!(ans); break; } } println!("{}", ans); }