#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define endl '\n' #define pb push_back #define fst first #define scd second #define EPS (1e-7) #define INF (1e9) #define PI (acos(-1)) #define ALL(x) (x).begin(), (x).end() #define RALL(x) (x).rbegin(), (x).rend() #define REP(i,n) for(int i = 0;i < (n);i++) #define FOR(i,a,b) for(int i = (a);i <= (b);i++) #define YES(n) cout << ((n) ? "YES" : "NO" ) << endl #define Yes(n) cout << ((n) ? "Yes" : "No" ) << endl constexpr int MOD = 1000000007; typedef long long ll; typedef unsigned long long ull; typedef pair P; typedef vector vi; typedef vector> vii; typedef vector vl; template T in() { T x; cin >> x; return (x); } template void out(T x) { cout << (x) << endl; } ll gcd(ll a, ll b) { return b ? gcd(b, a%b) : a; } // value ll N; vector> cake; vector, ll>> m_cake; void solve() { cin >> N; cake.resize(N, vector(3)); for (ll i = 0; i < N; i++) { ll tmp1, tmp2, tmp3; cin >> tmp1 >> tmp2 >> tmp3; cake[i][0] = tmp1; cake[i][1] = tmp2; cake[i][2] = tmp3; } sort(ALL(cake), [](vector v1, vector v2) { if (v1[0] != v2[0]) { return v1[0] < v2[0]; } else { return v1[1] < v2[1]; } }); m_cake.pb(make_pair(vector(1, 0), 0)); for (int i = 0; i < N;) { ll tmp = cake[i][0]; ll tmp3 = i; for (int j = i; i < N && cake[j][0] == tmp; j++, i++) { pair,ll> tmp2 = make_pair(vector(1,i), cake[i][2]); for (int k = 0; k < tmp3; k++) { vector tmp_cake = m_cake[k+1].fst; ll tmp_cal = m_cake[k+1].scd; if (cake[i][0] > cake[tmp_cake.back()][0] && cake[i][1] > cake[tmp_cake.back()][1]) { if (tmp2.scd < tmp_cal + cake[i][2]) { tmp_cake.pb(i); tmp2.fst = tmp_cake; tmp2.scd = tmp_cal + cake[i][2]; } } } m_cake.pb(tmp2); } } sort(ALL(m_cake), [](pair, ll> &p1, pair, ll> &p2) { return p1.scd > p2.scd; }); cout << m_cake[0].scd << endl; return; } int main() { cin.tie(0); ios::sync_with_stdio(false); solve(); return 0; }