#include using namespace std; #define pb push_back #define mp make_pair #define all(x) (x).begin(),(x).end() #define rep(i,n) for(int i=0;i<(n);i++) constexpr int MOD = 1000000007; typedef long long ll; typedef unsigned long long ull; typedef pair pii; constexpr int dx[] = {1, 0, -1, 0, 1, 1, -1, -1}; constexpr int dy[] = {0, -1, 0, 1, 1, -1, -1, 1}; template 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;} struct Phone { int h, w, t; bool operator<(const Phone &rhs) const { if (h == rhs.h) { return w > rhs.w; } return h < rhs.h; } }; struct BIT { vector data; BIT(int n): data(n + 1) {} ll getmax(int a) { ll ret = 0; for(int i = a; i > 0; i -= i & -i) { ret = max(ret, data[i]); } return ret; } void update(int a, ll w) { for(int i = a; i < data.size(); i += i & -i) { data[i] = max(data[i], w); } } }; // BIT解(想定解) ll solve1(int N, vector &P) { sort(all(P)); vector W(N); for (int i = 0; i < N; i++) { W[i] = P[i].w; } sort(all(W)); W.erase(unique(W.begin(), W.end()), W.end()); BIT bit(N + 2); for(int i = 0; i < N; i++) { int k = lower_bound(all(W), P[i].w) - W.begin() - 1; k += 2; // for BIT ll mi = bit.getmax(k); bit.update(k + 1, mi + P[i].t); } return bit.getmax(N + 2); } // Naive DP解(O(N^2), TLE) ll solve2(int N, vector &P) { sort(all(P)); vector dp(N, 0); for(int i = 0; i < N; i++) { ll ma = 0; for(int j = 0; j < i; j++) { if (P[j].w >= P[i].w) continue; ma = max(ma, dp[j]); } dp[i] = ma + P[i].t; } return *max_element(all(dp)); } void solve() { int N; cin >> N; if (N < 1 || N > 200000) exit(1); map M; for(int i = 0; i < N; i++) { int h, w, t; cin >> h >> w >> t; if (h < 1 || h > 1000000000) exit(1); if (w < 1 || w > 1000000000) exit(1); if (t < 1 || t > 1000000000) exit(1); M[{h, w}] = max(M[{h, w}], t); } vector P; for(auto &&x : M) { P.push_back({x.first.first, x.first.second, x.second}); } N = P.size(); if (N > 2000) { cout << solve1(N, P) << endl; } else { ll ans1 = solve1(N, P); ll ans2 = solve2(N, P); if (ans1 != ans2) { cout << "Error: " << ans1 << " : " << ans2 << endl; } else { cout << ans1 << endl; } } } int main() { std::cin.tie(0); std::ios::sync_with_stdio(false); cout.setf(ios::fixed); cout.precision(16); solve(); return 0; }