#![allow(unused_imports)] fn main() { input! { n: usize, t: usize, target: [(usize, usize, u64); n], } let m = target.iter().map(|t| t.1).max().unwrap(); let mut event = vec![(vec![], vec![]); m+1]; for (i, &(l, r, _)) in target.iter().enumerate() { event[l].0.push(i); event[r].1.push(i); } let mut dp = vec![0; m+1]; let mut set = BTreeSet::new(); for i in 0..=m { for &i in &event[i].0 { set.insert((target[i].2, i)); } if i > 0 { dp[i] = dp[i].max(dp[i-1]); } dp[i] = dp[i].max( set.last().map_or(0, |e| e.0) + if i >= t { dp[i-t] } else { 0 } ); for &i in &event[i].1 { set.remove(&(target[i].2, i)); } } println!("{}", dp[m]); } use proconio::{input, marker::*}; use std::{cmp::Reverse, collections::*}; #[macro_export] macro_rules! chmax { ($a:expr, $b:expr) => {{ let tmp = $b; if $a < tmp { $a = tmp; true } else { false } }}; } #[macro_export] macro_rules! chmin { ($a:expr, $b:expr) => {{ let tmp = $b; if $a > tmp { $a = tmp; true } else { false } }}; } #[macro_export] /// mvec![] macro_rules! mvec { ($val:expr; ()) => { $val }; ($val:expr; ($size:expr $(,$rest:expr)*)) => { vec![mvec![$val; ($($rest),*)]; $size] }; }