use rbtree::{Op, RbTree}; 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.get(b).max(c + dp.fold(..b).unwrap_or(0)); dp.delete(b); dp.insert(b, value); } let ans = dp.fold(..).unwrap(); println!("{}", ans); } enum O {} impl Op for O { type Summary = u64; type Value = u64; fn summarize(value: &Self::Value) -> Self::Summary { *value } fn op(lhs: Self::Summary, rhs: Self::Summary) -> Self::Summary { lhs.max(rhs) } } // rbtree {{{ #[allow(dead_code)] mod rbtree { #![warn(missing_docs)] mod nonempty { use { super::{Nop, Op}, std::{ cmp::Ordering, hash::{Hash, Hasher}, marker::PhantomData, mem::swap, }, }; pub enum Nonempty = Nop> { Nil(Nil), Internal(Box>), } #[derive(Clone, Debug, Default, Hash, PartialEq, Eq, Copy)] pub struct Nil(pub T); pub struct Internal> { pub left: Nonempty, pub right: Nonempty, pub height: usize, pub len: usize, pub summary: O::Summary, pub __marker: PhantomData O>, } impl> Internal { pub fn update(&mut self) { self.len = self.left.len() + self.right.len(); self.summary = O::op(self.left.summary(), self.right.summary()); } } impl> Nonempty { pub fn len(&self) -> usize { match self { Self::Nil(_) => 1, Self::Internal(node) => node.len, } } pub fn not_all_partition_point(&self, init: Option, f: F) -> usize where O::Summary: Clone, F: Fn(&O::Summary) -> bool, { match self { Self::Nil(Nil(x)) => { let x = O::summarize(x); let init = match init { None => x, Some(init) => O::op(init, x), }; if f(&init) { 1 } else { 0 } } Self::Internal(node) => { let linit = match init.clone() { None => node.left.summary(), Some(init) => O::op(init, node.left.summary()), }; if f(&linit) { node.left.len() + node.right.not_all_partition_point(Some(linit), f) } else { node.left.not_all_partition_point(init, f) } } } } pub fn fold(&self, start: usize, end: usize) -> O::Summary { debug_assert!(start < end && end <= self.len()); match self { Self::Nil(Nil(x)) => O::summarize(x), Self::Internal(node) => { let lsize = node.left.len(); if start == 0 && end == self.len() { node.summary.clone() } else if end <= lsize { node.left.fold(start, end) } else if lsize <= start { node.right.fold(start - lsize, end - lsize) } else { O::op( node.left.fold(start, lsize), node.right.fold(0, end - lsize), ) } } } } pub fn split(self, i: usize) -> [Self; 2] { let node = self.into_node().unwrap(); let left_len = node.left.len(); match i.cmp(&left_len) { Ordering::Equal => [node.left, node.right], Ordering::Less => { let [l, r] = node.left.split(i); [l, Self::merge(r, node.right)] } Ordering::Greater => { let [l, r] = node.right.split(i - left_len); [Self::merge(node.left, l), r] } } } pub fn merge(mut lhs: Self, mut rhs: Self) -> Self { let h = lhs.height(); match h.cmp(&rhs.height()) { Ordering::Equal => Self::from_children(lhs, rhs, h + 1), Ordering::Less => { rhs.merge_front(lhs); rhs } Ordering::Greater => { lhs.merge_back(rhs); lhs } } } pub fn merge_front(&mut self, other: Self) { let h = self.height(); if other.height() == self.node().unwrap().left.height() { let Internal { left, .. } = self.node_mut().unwrap(); replace_with(left, |x| Self::from_children(other, x, h)); } else { self.node_mut().unwrap().left.merge_front(other); } if self.node().unwrap().left.node().unwrap().left.height() == h { if self.node().unwrap().right.height() == h { self.node_mut().unwrap().height += 1; } else { let Internal { left, right, .. } = self.node_mut().unwrap(); swap(left, right); let l = left; let Internal { left, right, .. } = right.node_mut().unwrap(); swap(l, left); swap(left, right); self.node_mut().unwrap().right.node_mut().unwrap().update(); } } self.node_mut().unwrap().update(); } pub fn merge_back(&mut self, other: Self) { let h = self.height(); if other.height() == self.node().unwrap().right.height() { let Internal { right, .. } = self.node_mut().unwrap(); replace_with(right, |x| Self::from_children(x, other, h)); } else { self.node_mut().unwrap().right.merge_back(other); } if self.node().unwrap().right.node().unwrap().right.height() == h { if self.node().unwrap().left.height() == h { self.node_mut().unwrap().height += 1; } else { let Internal { left, right, .. } = self.node_mut().unwrap(); swap(left, right); let r = right; let Internal { left, right, .. } = left.node_mut().unwrap(); swap(right, r); swap(left, right); self.node_mut().unwrap().left.node_mut().unwrap().update(); } } self.node_mut().unwrap().update(); } pub fn node(&self) -> Option<&Internal> { match self { Self::Nil(_) => None, Self::Internal(node) => Some(node), } } pub fn node_mut(&mut self) -> Option<&mut Internal> { match self { Self::Nil(_) => None, Self::Internal(node) => Some(node), } } pub fn summary(&self) -> O::Summary { match self { Self::Nil(Nil(x)) => O::summarize(x), Self::Internal(node) => node.summary.clone(), } } fn into_node(self) -> Option> { match self { Self::Nil(_) => None, Self::Internal(node) => Some(*node), } } #[allow(clippy::wrong_self_convention)] fn from_children(lhs: Self, rhs: Self, height: usize) -> Self { Self::Internal(Box::new(Internal { len: lhs.len() + rhs.len(), summary: O::op(lhs.summary(), rhs.summary()), height, left: lhs, right: rhs, __marker: PhantomData, })) } fn height(&self) -> usize { match self { Self::Nil(_) => 0, Self::Internal(node) => node.height, } } } fn replace_with T>(dest: &mut T, f: F) { unsafe { std::ptr::write(dest, f(std::ptr::read(dest))) } } impl> Clone for Nonempty where O::Summary: Clone, { fn clone(&self) -> Self { match self { Self::Nil(x) => Self::Nil(x.clone()), Self::Internal(x) => Self::Internal(x.clone()), } } } impl> Clone for Internal where O::Summary: Clone, { fn clone(&self) -> Self { Self { left: self.left.clone(), right: self.right.clone(), height: self.height, len: self.len, summary: self.summary.clone(), __marker: self.__marker, } } } impl> PartialEq for Nonempty where O::Summary: PartialEq, { fn eq(&self, other: &Self) -> bool { match [self, other] { [Self::Nil(x), Self::Nil(y)] => x.eq(y), [Self::Internal(x), Self::Internal(y)] => x.eq(y), _ => false, } } } impl> PartialEq for Internal where O::Summary: PartialEq, { fn eq(&self, other: &Self) -> bool { self.left.eq(&other.left) && self.right.eq(&other.right) && self.height.eq(&other.height) && self.len.eq(&other.len) && self.summary.eq(&other.summary) } } impl> Hash for Nonempty where O::Summary: Hash, { fn hash(&self, state: &mut H) { match self { Self::Nil(x) => x.hash(state), Self::Internal(x) => x.hash(state), } } } impl> Hash for Internal where O::Summary: Hash, { fn hash(&self, state: &mut H) { self.left.hash(state); self.right.hash(state); self.height.hash(state); self.len.hash(state); self.summary.hash(state); } } } use { nonempty::{Nil, Nonempty}, std::{ fmt::{self, Debug}, hash::{Hash, Hasher}, iter::FromIterator, marker::PhantomData, mem::take, ops::{Bound, Range, RangeBounds}, }, }; pub struct RbTree = Nop>(Option>); pub trait Op { type Value; type Summary: Clone; fn summarize(value: &Self::Value) -> Self::Summary; fn op(lhs: Self::Summary, rhs: Self::Summary) -> Self::Summary; } pub struct Nop { __marker: PhantomData T>, } impl Op for Nop { type Value = T; type Summary = (); fn summarize(_value: &Self::Value) -> Self::Summary {} fn op(_lhs: Self::Summary, _rhs: Self::Summary) -> Self::Summary {} } impl> FromIterator for RbTree { fn from_iter>(iter: T) -> Self { let mut nodes = iter.into_iter().map(Self::singleton).collect::>(); if nodes.is_empty() { return Self::default(); } let mut step = 1; while step < nodes.len() { for i in (0..nodes.len() - step).step_by(2 * step) { nodes[i] = Self::merge(take(&mut nodes[i]), take(&mut nodes[i + step])); } step *= 2; } take(&mut nodes[0]) } } pub struct Iter<'a, T, O: Op>(Vec<&'a Nonempty>); impl<'a, T, O: Op> Iterator for Iter<'a, T, O> { type Item = &'a T; fn next(&mut self) -> Option { loop { match self.0.pop() { None => return None, Some(Nonempty::Nil(Nil(x))) => return Some(x), Some(Nonempty::Internal(node)) => { self.0.push(&node.right); self.0.push(&node.left); } } } } } impl> RbTree { pub fn new() -> Self { Self(None) } pub fn is_empty(&self) -> bool { self.0.is_none() } pub fn len(&self) -> usize { match &self.0 { None => 0, Some(node) => node.len(), } } pub fn iter(&self) -> Iter<'_, T, O> { Iter(match &self.0 { None => Vec::new(), Some(node) => vec![node], }) } pub fn get(&mut self, i: usize) -> T where T: Copy, { assert!((0..self.len()).contains(&i)); let root = take(&mut self.0).unwrap(); let [l, cr] = Self(Some(root)).split(i); let [c, r] = cr.split(1); let res = match c.0.as_ref().unwrap() { Nonempty::Nil(nil) => nil.0, Nonempty::Internal(_) => unreachable!(), }; *self = Self::merge(Self::merge(l, c), r); res } pub fn partition_point(&self, f: F) -> usize where O::Summary: Clone, F: Fn(&O::Summary) -> bool, { match self.0.as_ref() { None => 0, Some(nonempty) => { if f(&nonempty.summary()) { self.len() } else { nonempty.not_all_partition_point(None, f) } } } } pub fn fold(&self, range: impl RangeBounds) -> Option { let Range { start, end } = open(range, self.len()); assert!(start <= end && end <= self.len()); if start == end { None } else { Some(self.0.as_ref().unwrap().fold(start, end)) } } pub fn singleton(x: T) -> Self { Self(Some(Nonempty::Nil(Nil(x)))) } pub fn push_front(&mut self, x: T) { *self = Self::merge(Self::singleton(x), take(self)); } pub fn push_back(&mut self, x: T) { *self = Self::merge(take(self), Self::singleton(x)); } pub fn insert(&mut self, i: usize, x: T) { assert!((0..=self.len()).contains(&i)); let [l, r] = take(self).split(i); *self = Self::merge3(l, Self::singleton(x), r); } pub fn delete(&mut self, i: usize) -> T { assert!((0..self.len()).contains(&i)); let [l, c, r] = take(self).split3(i, i + 1); *self = Self::merge(l, r); match c.0 { Some(Nonempty::Internal(_)) | None => unreachable!(), Some(Nonempty::Nil(Nil(value))) => value, } } pub fn merge(lhs: Self, rhs: Self) -> Self { match [lhs.0, rhs.0] { [None, None] => Self(None), [Some(l), None] => Self(Some(l)), [None, Some(r)] => Self(Some(r)), [Some(l), Some(r)] => Self(Some(Nonempty::merge(l, r))), } } pub fn merge3(x: Self, y: Self, z: Self) -> Self { Self::merge(Self::merge(x, y), z) } pub fn split(self, i: usize) -> [Self; 2] { assert!((0..=self.len()).contains(&i)); if i == 0 { [Self(None), self] } else if i == self.len() { [self, Self(None)] } else { let [l, r] = self.0.unwrap().split(i); [Self(Some(l)), Self(Some(r))] } } pub fn split3(self, start: usize, end: usize) -> [Self; 3] { let [xy, z] = self.split(end); let [x, y] = xy.split(start); [x, y, z] } } impl> Clone for RbTree where O::Summary: Clone, { fn clone(&self) -> Self { Self(self.0.clone()) } } impl> PartialEq for RbTree where O::Summary: PartialEq, { fn eq(&self, other: &Self) -> bool { self.0.eq(&other.0) } } impl> Hash for RbTree where O::Summary: Hash, { fn hash(&self, state: &mut H) { self.0.hash(state); } } impl> Debug for RbTree { fn fmt(&self, f: &mut fmt::Formatter<'_>) -> fmt::Result { f.debug_list().entries(self.iter()).finish() } } impl> Default for RbTree { fn default() -> Self { Self::new() } } fn open(range: impl RangeBounds, len: usize) -> Range { (match range.start_bound() { Bound::Unbounded => 0, Bound::Included(&x) => x, Bound::Excluded(&x) => x + 1, })..match range.end_bound() { Bound::Excluded(&x) => x, Bound::Included(&x) => x + 1, Bound::Unbounded => len, } } } // }}} // 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)) } } // }}}