use proconio::input; const M: usize = 200_010; fn main() { input! { n: usize, t: usize, mut targets: [(usize, usize, usize); n], } targets.sort_unstable_by_key(|t| t.2); let mut best = lazy_segtree::LazySegmentTree::::new(M); for &(l, r, p) in &targets { best.apply_range(l, r + 1, Some(p)); } let mut dp = vec![0; M]; for i in 1..M { dp[i] = dp[i].max(dp[i - 1]); if i >= t { dp[i] = dp[i].max(dp[i - t] + best.get(i - t)); } } let ans = dp[M - 1]; println!("{ans}"); } struct RangeUpdate; impl lazy_segtree::Operator for RangeUpdate { type Value = usize; type Map = Option; fn identity() -> Self::Value { 0 } fn identity_map() -> Self::Map { None } fn op(a: &Self::Value, b: &Self::Value) -> Self::Value { *a + *b } fn apply(f: &Self::Map, x: &Self::Value) -> Self::Value { f.unwrap_or(*x) } fn compose(f: &Self::Map, g: &Self::Map) -> Self::Map { f.or(*g) } } #[allow(unused)] mod lazy_segtree { pub trait Operator { type Value: Clone; type Map: Clone; fn identity() -> Self::Value; fn identity_map() -> Self::Map; fn op(a: &Self::Value, b: &Self::Value) -> Self::Value; fn apply(f: &Self::Map, x: &Self::Value) -> Self::Value; fn compose(f: &Self::Map, g: &Self::Map) -> Self::Map; } pub struct LazySegmentTree { n: usize, offset: usize, height: usize, value: Vec, map: Vec, } impl From> for LazySegmentTree { fn from(v: Vec) -> Self { let n = v.len(); let offset = n.next_power_of_two(); let height = offset.trailing_zeros() as usize; let mut value = vec![O::identity(); 2 * offset]; value[offset..][..n].clone_from_slice(&v); let map = vec![O::identity_map(); offset]; let mut ret = Self { n, offset, height, value, map, }; for i in (1..offset).rev() { ret.update(i); } ret } } impl LazySegmentTree { pub fn new(n: usize) -> Self { vec![O::identity(); n].into() } pub fn as_slice(&mut self) -> &[O::Value] { for i in 1..self.offset { self.push(i); } &self.value[self.offset..][..self.n] } pub fn get(&mut self, i: usize) -> O::Value { debug_assert!(i < self.n); let i = i + self.offset; for k in (1..=self.height).rev() { self.push(i >> k); } self.value[i].clone() } pub fn set(&mut self, i: usize, x: O::Value) { debug_assert!(i < self.n); let i = i + self.offset; for k in (1..=self.height).rev() { self.push(i >> k); } self.value[i] = x; for k in 1..=self.height { self.update(i >> k); } } pub fn prod(&mut self, l: usize, r: usize) -> O::Value { debug_assert!(l <= r && r <= self.n); let (mut l, mut r) = (l + self.offset, r + self.offset); for k in (1..=self.height).rev() { if ((l >> k) << k) != l { self.push(l >> k); } if ((r >> k) << k) != r { self.push(r >> k); } } let mut prod_l = O::identity(); let mut prod_r = O::identity(); while l < r { if l & 1 == 1 { prod_l = O::op(&prod_l, &self.value[l]); l += 1; } if r & 1 == 1 { prod_r = O::op(&self.value[r - 1], &prod_r); } l >>= 1; r >>= 1; } O::op(&prod_l, &prod_r) } pub fn all_prod(&self) -> O::Value { self.value[1].clone() } pub fn apply(&mut self, i: usize, f: O::Map) { debug_assert!(i < self.n); let i = i + self.offset; for k in (1..=self.height).rev() { self.push(i >> k); } self.value[i] = O::apply(&f, &self.value[i]); for k in 1..=self.height { self.update(i >> k); } } pub fn apply_range(&mut self, l: usize, r: usize, f: O::Map) { debug_assert!(l <= r && r <= self.n); let (l, r) = (l + self.offset, r + self.offset); for k in (1..=self.height).rev() { if ((l >> k) << k) != l { self.push(l >> k); } if ((r >> k) << k) != r { self.push(r >> k); } } { let (mut l, mut r) = (l, r); while l < r { if l & 1 == 1 { self.all_apply(l, &f); l += 1; } if r & 1 == 1 { self.all_apply(r - 1, &f); } l >>= 1; r >>= 1; } } for k in 1..=self.height { if ((l >> k) << k) != l { self.update(l >> k); } if ((r >> k) << k) != r { self.update(r >> k); } } } pub fn max_right(&mut self, l: usize, f: impl Fn(&O::Value) -> bool) -> usize { debug_assert!(l <= self.n); debug_assert!(f(&O::identity())); let mut i = l + self.offset; for k in (1..=self.height).rev() { self.push(i >> k); } let mut prod = O::identity(); loop { i >>= i.trailing_zeros(); let next = O::op(&prod, &self.value[i]); if !f(&next) { break; } i += 1; prod = next; if i & i.wrapping_neg() == i { return self.n; } } while i < self.offset { self.push(i); i *= 2; let next = O::op(&prod, &self.value[i]); if f(&next) { i += 1; prod = next; } } i - self.offset } pub fn min_left(&mut self, r: usize, f: impl Fn(&O::Value) -> bool) -> usize { debug_assert!(r <= self.n); debug_assert!(f(&O::identity())); let mut i = r + self.offset; for k in (1..=self.height).rev() { self.push((i - 1) >> k); } let mut prod = O::identity(); loop { i >>= i.trailing_zeros(); if i > 1 { i -= 1; } let next = O::op(&self.value[i], &prod); if !f(&next) { break; } prod = next; if i & i.wrapping_neg() == i { return 0; } } while i < self.offset { self.push(i); i = 2 * i + 1; let next = O::op(&self.value[i], &prod); if f(&next) { i -= 1; prod = next; } } i + 1 - self.offset } fn update(&mut self, i: usize) { self.value[i] = O::op(&self.value[2 * i], &self.value[2 * i + 1]); } fn all_apply(&mut self, i: usize, f: &O::Map) { self.value[i] = O::apply(f, &self.value[i]); if i < self.offset { self.map[i] = O::compose(f, &self.map[i]); } } fn push(&mut self, i: usize) { let f = std::mem::replace(&mut self.map[i], O::identity_map()); self.all_apply(2 * i, &f); self.all_apply(2 * i + 1, &f); } } }