#include using namespace std; /*{{{*/ //template #define rep(i,n) for(int i=0;i<(int)(n);i++) constexpr int INF = numeric_limits::max()/2; constexpr long long LINF = numeric_limits::max()/3; #define pb push_back #define eb emplace_back #define fi first #define se second #define all(v) (v).begin(),(v).end() #define sz(x) (int)(x).size() #define debug(x) cerr<<#x<<":"< ostream& operator<<(ostream& os,const vector& vec){ os << "["; for(const auto& v : vec){ os << v << ","; } os << "]"; return os; } template ostream& operator<<(ostream& os,const pair& p){ os << "(" << p.first << ","<< p.second <<")"; return os; } template ostream& operator<<(ostream& os,const set& st){ os<<"{"; for(T v:st) os< inline void chmax(T &x,U y){ if(y>x) x = y; } template inline void chmin(T &x,U y){ if(y pii; typedef vector vi; typedef vector vvi; ll gcd(ll a,ll b){ if(b==0) return a; else return gcd(b,a%b); } //constexpr double eps = 1e-14; constexpr double eps = 1e-10; constexpr ll mod = 1e9+7; const int dx[]={1,0,-1,0} ,dy[] = {0,1,0,-1}; /*}}}*/ /* * Range Maximum Query * * T データ型 * iniv 初期値 */ template struct Segtree{ int n; vector dat; Segtree(int n_){ n = 1; while(n < n_) n *= 2; dat.resize(2*n-1); for(int i=0;i<2*n-1;i++) dat[i]=iniv; } void update(int k,T a){ k+=n-1; dat[k]=a; while(k>0){ k=(k-1)/2; dat[k]=max(dat[k*2+1],dat[k*2+2]); } } T query(int a,int b,int k,int l,int r){ if(r<=a or b<=l) return iniv; else if(a<=l and r<=b) return dat[k]; else{ T vl = query(a,b,k*2+1,l,(l+r)/2); T vr = query(a,b,k*2+2,(l+r)/2,r); return max(vl,vr); } } T query(int a,int b){ return query(a,b,0,0,n); } }; using P = tuple; ostream& operator<<(ostream& os,const P& p){ ll a,b,c; tie(a,b,c) = p;os << "(" << a << ","<< b <<","< cakes(N); rep(i,N){ ll a,b,c; scanf("%lld %lld %lld",&a,&b,&c); b *= -1; cakes[i] = make_tuple(a,b,c); } sort(all(cakes)); for(int i=0;i(cakes[i]); b *= -1; } map mp; for(int i=0;i(cakes[i])] = 0; } int id = 0; for(auto& b : mp){ b.second = id++; } for(int i=0;i(cakes[i]); b = mp[b]; } Segtree seg(N); vector dp(N+10,0); for(int i=0;i(cakes[i]); ll c = get<2>(cakes[i]); ll q = seg.query(0,b); dp[i] = q + c; seg.update(b,dp[i]); } ll ans = 0; for(int i=0;i