#include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define REP(i, n) for (int i = 0; i < n; i++) #define FOR(i, s, t) for (int i = s; i < t; i++) #define ALL(obj) obj.begin(), obj.end() const int iINF = 1e9; const long long llINF = 1e18; const int MOD = 1e9 + 7; template inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; } template inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; } template struct ModInt { long long val; constexpr ModInt(long long v = 0) noexcept : val(v % MOD) { if (val < 0) val += MOD; } constexpr int getmod() { return MOD; } constexpr ModInt operator-() const noexcept { return val ? MOD - val : 0; } constexpr ModInt operator+(const ModInt& r) const noexcept { return ModInt(*this) += r; } constexpr ModInt operator-(const ModInt& r) const noexcept { return ModInt(*this) -= r; } constexpr ModInt operator*(const ModInt& r) const noexcept { return ModInt(*this) *= r; } constexpr ModInt operator/(const ModInt& r) const noexcept { return ModInt(*this) /= r; } constexpr ModInt& operator+=(const ModInt& r) noexcept { val += r.val; if (val >= MOD) val -= MOD; return *this; } constexpr ModInt& operator-=(const ModInt& r) noexcept { val -= r.val; if (val < 0) val += MOD; return *this; } constexpr ModInt& operator*=(const ModInt& r) noexcept { val = val * r.val % MOD; return *this; } constexpr ModInt& operator/=(const ModInt& r) noexcept { long long a = r.val, b = MOD, u = 1, v = 0; while (b) { long long t = a / b; a -= t * b; swap(a, b); u -= t * v; swap(u, v); } val = val * u % MOD; if (val < 0) val += MOD; return *this; } constexpr bool operator==(const ModInt& r) const noexcept { return this->val == r.val; } constexpr bool operator!=(const ModInt& r) const noexcept { return this->val != r.val; } friend constexpr ostream& operator<<(ostream& os, const ModInt& x) noexcept { return os << x.val; } friend constexpr istream& operator>>(istream& is, ModInt& x) noexcept { return is >> x.val; } friend constexpr ModInt modpow(const ModInt& a, long long n) noexcept { if (n == 0) return 1; auto t = modpow(a, n / 2); t = t * t; if (n & 1) t = t * a; return t; } }; using mint = ModInt; long long modPow(long long x, long long n, long long mod) { long long res = 1; while (n > 0) { if (n & 1) res = res * x % mod; x = x * x % mod; n >>= 1; } return res; } long long extGCD(long long a, long long b, long long& x, long long& y) { if (b == 0) { x = 1; y = 0; return a; } long long d = extGCD(b, a % b, y, x); y -= a / b * x; return d; } long long gcd(long long a, long long b) { if (b == 0) { return a; } else { return gcd(b, a % b); } } long long lcm(long long a, long long b) { return a / gcd(a, b) * b; } template map compress(vector x) { map res; sort(x.begin(), x.end()); x.erase(unique(x.begin(), x.end()), x.end()); for (int i = 0; i < x.size(); i++) { res[x[i]] = i; } return res; } template int former(const vector& v, T x) { return upper_bound(v.begin(), v.end(), x) - v.begin() - 1; } template int latter(const vector& v, T x) { return lower_bound(v.begin(), v.end(), x) - v.begin(); } template using Vec = vector; template using VVec = vector>; using LL = long long; template struct LazySegmentTree { using MMtoM = function; using OOtoO = function; using MOtoM = function; using OItoO = function; // node, lazy, update flag (for lazy), identity element int n; vector node; vector lazy; vector need_update; MonoidType E0; OperatorType E1; // update / combine / lazy / accumulate function MOtoM upd_f; MMtoM cmb_f; OOtoO lzy_f; OItoO acc_f; void build(int m, vector v = vector()) { if (v != vector()) m = v.size(); n = 1; while (n < m) n *= 2; node = vector(2 * n - 1, E0); lazy = vector(2 * n - 1, E1); need_update = vector(2 * n - 1, false); if (v != vector()) { for (int i = 0; i < m; i++) { node[n - 1 + i] = v[i]; } for (int i = n - 2; i >= 0; i--) { node[i] = cmb_f(node[2 * i + 1], node[2 * i + 2]); } } } // initialize LazySegmentTree() {} LazySegmentTree(int n_, MonoidType E0_, OperatorType E1_, MOtoM upd_f_, MMtoM cmb_f_, OOtoO lzy_f_, OItoO acc_f_, vector v = vector()) : E0(E0_), E1(E1_), upd_f(upd_f_), cmb_f(cmb_f_), lzy_f(lzy_f_), acc_f(acc_f_) { build(n_, v); } void eval(int k, int l, int r) { if (!need_update[k]) return; node[k] = upd_f(node[k], acc_f(lazy[k], r - l)); if (r - l > 1) { lazy[2 * k + 1] = lzy_f(lazy[2 * k + 1], lazy[k]); lazy[2 * k + 2] = lzy_f(lazy[2 * k + 2], lazy[k]); need_update[2 * k + 1] = need_update[2 * k + 2] = true; } lazy[k] = E1; need_update[k] = false; } void update(int a, int b, OperatorType x, int l, int r, int k) { eval(k, l, r); if (b <= l or r <= a) return; if (a <= l and r <= b) { lazy[k] = lzy_f(lazy[k], x); need_update[k] = true; eval(k, l, r); } else { int mid = (l + r) / 2; update(a, b, x, l, mid, 2 * k + 1); update(a, b, x, mid, r, 2 * k + 2); node[k] = cmb_f(node[2 * k + 1], node[2 * k + 2]); } } MonoidType query(int a, int b, int l, int r, int k) { if (b <= l or r <= a) return E0; eval(k, l, r); if (a <= l and r <= b) return node[k]; int mid = (l + r) / 2; MonoidType vl = query(a, b, l, mid, 2 * k + 1); MonoidType vr = query(a, b, mid, r, 2 * k + 2); return cmb_f(vl, vr); } // update [a, b)-th element (applied value, x) void update(int a, int b, OperatorType x) { update(a, b, x, 0, n, 0); } // range query for [a, b) MonoidType query(int a, int b) { return query(a, b, 0, n, 0); } }; int main() { int N; cin >> N; LazySegmentTree dp( N + 1, 0, 0, [](LL a, LL b) { return b; }, [](LL a, LL b) { return max(a, b); }, [](LL a, LL b) { return b; }, [](LL a, int x) { return a; }); Vec A(N), B(N), C(N); REP(i, N) { cin >> A[i] >> B[i] >> C[i]; } map zipB; Vec unzipB; unzipB = B; sort(ALL(unzipB)); unzipB.erase(unique(ALL(unzipB)), unzipB.end()); REP(i, unzipB.size()) { zipB[unzipB[i]] = i; } Vec ord; REP(i, N) ord.push_back(i); sort(ALL(ord), [&](LL a, LL b) { if (A[a] == A[b]) return B[a] > B[b]; else return A[a] < A[b]; }); REP(i, N) { LL tmp = dp.query(0, zipB[B[ord[i]]]) + C[ord[i]]; chmax(tmp, dp.query(zipB[B[ord[i]]], zipB[B[ord[i]]] + 1)); dp.update(zipB[B[ord[i]]], zipB[B[ord[i]]] + 1, tmp); } cout << dp.query(0, N + 1) << endl; return 0; }