use crate::segtree::Segtree; use segtree::Ops; use slicemore::SliceMore; use std::{cmp::Reverse, convert::TryFrom, io::stdin, iter::repeat_with}; fn main() { let stdin = stdin(); let mut stdin = stdin.lines().map(Result::unwrap); let n = stdin.next().unwrap().parse::().unwrap(); let mut abc = repeat_with(|| { <[_; 3]>::try_from( stdin .next() .unwrap() .split_whitespace() .map(|x| x.parse::().unwrap()) .collect::>(), ) .unwrap() }) .take(n) .collect::>(); abc.sort_by_key(|&[a, b, _]| (a, Reverse(b))); let mut b_sorted = abc.iter().map(|&[_, b, _]| b).collect::>(); b_sorted.sort(); let mut dp = vec![0; n].into_iter().collect::>(); for &[_, b, c] in &abc { let b = b_sorted.lower_bound(&b); let value = dp[b].max(c + dp.fold(..b)); change_max!(&mut *dp.entry(b), value); } let ans = dp.fold(..); println!("{}", ans); } enum O {} impl Ops for O { type Value = u64; fn op(lhs: &Self::Value, rhs: &Self::Value) -> Self::Value { (*lhs).max(*rhs) } fn identity() -> Self::Value { 0 } } // cmpmore {{{ #[allow(dead_code)] mod cmpmore { pub fn change_min(lhs: &mut T, rhs: T) { if *lhs > rhs { *lhs = rhs; } } pub fn change_max(lhs: &mut T, rhs: T) { if *lhs < rhs { *lhs = rhs; } } #[macro_export] macro_rules! change_min { ($lhs:expr, $rhs:expr) => { let rhs = $rhs; let lhs = $lhs; $crate::cmpmore::change_min(lhs, rhs); }; } #[macro_export] macro_rules! change_max { ($lhs:expr, $rhs:expr) => { let rhs = $rhs; let lhs = $lhs; $crate::cmpmore::change_max(lhs, rhs); }; } pub trait CmpMore: PartialOrd + Sized { fn change_min(&mut self, rhs: Self) { change_min(self, rhs) } fn change_max(&mut self, rhs: Self) { change_max(self, rhs) } } impl CmpMore for T {} } // }}} // segtree {{{ #[allow(dead_code)] mod segtree { use std::{ collections::VecDeque, fmt::Debug, iter::{repeat_with, FromIterator}, ops::{Bound, Deref, DerefMut, Index, Range, RangeBounds}, slice::SliceIndex, }; // 演算 pub trait Ops { type Value: Debug + Default; fn op(lhs: &Self::Value, rhs: &Self::Value) -> Self::Value; fn identity() -> Self::Value; } // 本体 pub struct Segtree { table: Box<[O::Value]>, } impl Segtree { pub fn new< I: ExactSizeIterator, T: IntoIterator, >( iter: T, ) -> Self { let iter = iter.into_iter(); let n = iter.len(); let mut table = repeat_with(O::Value::default).take(n).collect::>(); table.extend(iter); (1..n) .rev() .for_each(|i| table[i] = O::op(&table[2 * i], &table[2 * i + 1])); let table = table.into_boxed_slice(); Self { table } } pub fn is_empty(&self) -> bool { self.table.is_empty() } pub fn len(&self) -> usize { self.table.len() / 2 } pub fn fold(&self, range: impl RangeBounds) -> O::Value { let mut left = O::identity(); let mut right = O::identity(); let Range { mut start, mut end } = into_slice_range(self.len(), range); if end < start { segtree_index_order_fail(start, end); } if self.len() < end { segtree_end_index_len_fail(end, self.len()); } start += self.len(); end += self.len(); while start != end { if start % 2 == 1 { left = O::op(&left, &self.table[start]); start += 1; } if end % 2 == 1 { end -= 1; right = O::op(&self.table[end], &right); } start /= 2; end /= 2; } O::op(&left, &right) } pub fn max_right( &self, range: impl RangeBounds, mut pred: impl FnMut(&O::Value) -> bool, ) -> usize { let Range { mut start, mut end } = into_slice_range(self.len(), range); if start == end { start } else { start += self.len(); end += self.len(); let orig_end = end; let mut crr = O::identity(); let mut shift = 0; while start != end { if start % 2 == 1 { let nxt = O::op(&crr, &self.table[start]); if !pred(&nxt) { return self.max_right_subtree(crr, start, pred); } crr = nxt; start += 1; } start /= 2; end /= 2; shift += 1; } for p in (0..shift).rev() { let end = (orig_end >> p) - 1; if end % 2 == 0 { let nxt = O::op(&crr, &self.table[end]); if !pred(&nxt) { return self.max_right_subtree(crr, end, pred); } crr = nxt; } } orig_end - self.len() } } fn max_right_subtree( &self, mut crr: O::Value, mut root: usize, mut pred: impl FnMut(&O::Value) -> bool, ) -> usize { while root < self.len() { let nxt = O::op(&crr, &self.table[root * 2]); root = if pred(&nxt) { crr = nxt; root * 2 + 1 } else { root * 2 }; } root - self.len() } pub fn max_left( &self, range: impl RangeBounds, mut pred: impl FnMut(&O::Value) -> bool, ) -> usize { let Range { mut start, mut end } = into_slice_range(self.len(), range); if start == end { start } else { start += self.len(); end += self.len(); let orig_start_m1 = start - 1; let mut crr = O::identity(); let mut shift = 0; while start != end { if end % 2 == 1 { end -= 1; let nxt = O::op(&self.table[end], &crr); if !pred(&nxt) { return self.max_left_subtree(crr, end, pred); } crr = nxt; } start = (start + 1) >> 1; end >>= 1; shift += 1; } for p in (0..shift).rev() { let start = (orig_start_m1 >> p) + 1; if start % 2 == 1 { let nxt = O::op(&self.table[start], &crr); if !pred(&nxt) { return self.max_left_subtree(crr, start, pred); } crr = nxt; } } orig_start_m1 + 1 - self.len() } } fn max_left_subtree( &self, mut crr: O::Value, mut root: usize, mut pred: impl FnMut(&O::Value) -> bool, ) -> usize { while root < self.len() { let nxt = O::op(&self.table[root * 2 + 1], &crr); root = if pred(&nxt) { crr = nxt; root * 2 } else { root * 2 + 1 }; } root + 1 - self.len() } pub fn entry(&mut self, idx: usize) -> Entry<'_, O> { Entry { idx, seg: self } } pub fn as_slice(&self) -> &[O::Value] { self.as_ref() } pub fn as_slice_mut(&mut self) -> &mut [O::Value] { self.as_mut() } } // 要素アクセス impl> Index for Segtree { type Output = O::Value; fn index(&self, index: Idx) -> &Self::Output { &self.as_slice()[index] } } pub struct Entry<'a, O: Ops> { idx: usize, seg: &'a mut Segtree, } impl<'a, O: Ops> Drop for Entry<'a, O> { fn drop(&mut self) { self.idx += self.seg.len(); self.idx /= 2; while self.idx != 0 { self.seg.table[self.idx] = O::op( &self.seg.table[2 * self.idx], &self.seg.table[2 * self.idx + 1], ); self.idx /= 2; } } } impl Deref for Entry<'_, O> { type Target = O::Value; fn deref(&self) -> &Self::Target { &self.seg.as_slice()[self.idx] } } impl DerefMut for Entry<'_, O> { fn deref_mut(&mut self) -> &mut Self::Target { &mut self.seg.as_slice_mut()[self.idx] } } // 変換 impl From> for Segtree { fn from(v: Vec) -> Self { Self::new(v) } } impl FromIterator for Segtree { fn from_iter>(iter: T) -> Self { let mut v = iter.into_iter().collect::>(); let n = v.len(); let mut table = repeat_with(O::Value::default) .take(n) .collect::>(); table.append(&mut v); (1..n) .rev() .for_each(|i| table[i] = O::op(&table[2 * i], &table[2 * i + 1])); let table = Vec::from(table).into_boxed_slice(); Self { table } } } impl AsRef<[O::Value]> for Segtree { fn as_ref(&self) -> &[O::Value] { &self.table[self.len()..] } } impl AsMut<[O::Value]> for Segtree { fn as_mut(&mut self) -> &mut [O::Value] { let n = self.len(); &mut self.table[n..] } } // フォーマット impl Debug for Segtree { fn fmt(&self, f: &mut std::fmt::Formatter<'_>) -> std::fmt::Result { self.as_slice().fmt(f) } } // プライベート - RangeBounds 関連 fn into_slice_range(len: usize, range: impl RangeBounds) -> Range { #[allow(clippy::redundant_closure)] let start = match range.start_bound() { Bound::Included(&start) => start, Bound::Excluded(&start) => start .checked_add(1) .unwrap_or_else(|| slice_start_index_overflow_fail()), Bound::Unbounded => 0, }; #[allow(clippy::redundant_closure)] let end = match range.end_bound() { Bound::Included(&end) => end .checked_add(1) .unwrap_or_else(|| slice_end_index_overflow_fail()), Bound::Excluded(&end) => end, Bound::Unbounded => len, }; start..end } fn segtree_end_index_len_fail(index: usize, len: usize) -> ! { panic!( "range end index {} out of range for segtree of length {}", index, len ); } fn segtree_index_order_fail(index: usize, end: usize) -> ! { panic!("segtree index starts at {} but ends at {}", index, end); } fn slice_start_index_overflow_fail() -> ! { panic!("attempted to index slice from after maximum usize"); } fn slice_end_index_overflow_fail() -> ! { panic!("attempted to index slice up to maximum usize"); } // テスト } // }}} // slicemore {{{ #[allow(dead_code)] mod slicemore { use std::cmp::Ordering::{self, Equal, Greater, Less}; pub trait SliceMore { fn partition_point bool>(&self, pred: F) -> usize; fn lower_bound_by Ordering>(&self, f: F) -> usize; fn upper_bound_by Ordering>(&self, f: F) -> usize; fn lower_bound_by_key B>(&self, b: &B, f: F) -> usize; fn upper_bound_by_key B>(&self, b: &B, f: F) -> usize; fn lower_bound(&self, x: &T) -> usize where T: Ord; fn upper_bound(&self, x: &T) -> usize where T: Ord; } impl SliceMore for [T] { fn partition_point bool>(&self, pred: F) -> usize { partition_point(self, pred) } fn lower_bound_by Ordering>(&self, f: F) -> usize { lower_bound_by(self, f) } fn upper_bound_by Ordering>(&self, f: F) -> usize { upper_bound_by(self, f) } fn lower_bound_by_key B>(&self, b: &B, f: F) -> usize { lower_bound_by_key(self, b, f) } fn upper_bound_by_key B>(&self, b: &B, f: F) -> usize { upper_bound_by_key(self, b, f) } fn lower_bound(&self, x: &T) -> usize where T: Ord, { lower_bound(self, x) } fn upper_bound(&self, x: &T) -> usize where T: Ord, { upper_bound(self, x) } } pub fn partition_point bool>(slice: &[T], mut pred: F) -> usize { slice .binary_search_by(|x| if pred(x) { Less } else { Greater }) .unwrap_err() } pub fn lower_bound_by Ordering>(slice: &[T], mut f: F) -> usize { partition_point(slice, |x| matches!(f(x), Less)) } pub fn upper_bound_by Ordering>(slice: &[T], mut f: F) -> usize { partition_point(slice, |x| matches!(f(x), Less | Equal)) } pub fn lower_bound_by_key B>(slice: &[T], b: &B, mut f: F) -> usize { lower_bound_by(slice, |x| f(x).cmp(b)) } pub fn upper_bound_by_key B>(slice: &[T], b: &B, mut f: F) -> usize { upper_bound_by(slice, |x| f(x).cmp(b)) } pub fn lower_bound(slice: &[T], x: &T) -> usize { lower_bound_by(slice, |p| p.cmp(x)) } pub fn upper_bound(slice: &[T], x: &T) -> usize { upper_bound_by(slice, |p| p.cmp(x)) } } // }}}