#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include /* #include using namespace boost::multiprecision; */ using namespace std; using ll = long long; using ull = unsigned long long; #define REP(i,a,b) for(ll i = a; i < b; ++i) #define PRI(s) std::cout << s << endl #define PRIF(v, n) printf("%."#n"f\n", (double)v) templatevoid mins(A& a, const B& b) { a = min(a, (A)b); }; templatevoid maxs(A& a, const B& b) { a = max(a, (A)b); }; template class segtree { public: using func_xx = function; long long N; func_xx fxx; X ex; vector dat; bool changed; segtree() {} segtree(long long n, func_xx fxx, const X& ex) : fxx(fxx), ex(ex), changed(false) { if (n == 1) ++n; int x = 1; while (x < n) x *= 2; N = x; dat.resize(2 * N - 1, ex); } const segtree& operator=(const segtree& source) { N = source.N; fxx = source.fxx; ex = source.ex; dat = source.dat; changed = source.changed; return *this; } //代入後のデータ更新 void update(int k) { dat[k] = fxx(dat[2 * k + 1], dat[2 * k + 2]); if (k != 0) update((k - 1) / 2); } void build() { for (int i = N - 2; i >= 0; --i) dat[i] = fxx(dat[2 * i + 1], dat[2 * i + 2]); changed = false; } //要素の代入 void set(int i, const X& x, bool update = true) { dat[N - 1 + i] = x; if (update) this->update((N - 2 + i) / 2); else changed = true; } //要素の参照 const X& elem(int i) { return dat[N - 1 + i]; } X query_sub(int a, int b, int k, int l, int r) { if (r <= a || b <= l) { return ex; } else if (a <= l && r <= b) { return dat[k]; } else { return fxx(query_sub(a, b, 2 * k + 1, l, (l + r) / 2), query_sub(a, b, 2 * k + 2, (l + r) / 2, r)); } } //[a,b)間のクエリfxx X query(int a, int b) { if (changed) build(); return query_sub(a, b, 0, 0, N); } }; int main() { auto func = [](ll a, ll b) {return max(a, b); }; ll N; cin >> N; vector> abc(N); map>> mp; map ind; REP(i, 0, N) { ll a, b, c; cin >> a >> b >> c; abc[i] = { a,-b,c }; ind[b] = 0; maxs(mp[a][b], c); } ll c = 0; for (auto& p : ind) p.second = c++; /* sort(abc.begin(), abc.end()); c = 0; pair last = { 0,0 }; auto cmp = [](auto a, auto b) {if (a.first == b.first) return a.second > b.second; else return a.first < b.first; }; */ segtree seg{ N, func, 0 }; for (auto& v : mp)for (auto p : v.second) { //for (auto& v : abc) { //auto [a, b, c] = v; ll b = -p.first; ll c = p.second; ll tmp = seg.query(0, ind[-b]); if (seg.elem(ind[-b]) < tmp + c) seg.set(ind[-b], tmp + c); } PRI(seg.query(0, N)); return 0; }