// yukicoder: No.777 再帰的ケーキ // bal4u 2019.8.25 #include #include typedef long long ll; //// 高速入力 #if 1 #define gc() getchar_unlocked() #else #define gc() getchar() #endif int in() { // 非負整数の入力 int n = 0, c = gc(); do n = 10 * n + (c & 0xf); while ((c = gc()) >= '0'); return n; } inline static void chmax(ll *a, ll b) { if (*a < b) *a = b; } //// bit木 1-indexedに注意 #define MAX 200005 ll bit[MAX]; int bitn; //void add(int i) { while (i <= bitn) bit[i]++, i += i & -i; } //int sum(int i) { int s = 0; while (i > 0) s += bit[i], i -= i & -i; return s; } void update(int i, ll v) { while (i <= bitn && bit[i] < v) bit[i] = v, i += i & -i; } ll maxv(int i) { ll ma = 0; while (i > 0) chmax(&ma, bit[i]), i -= i & -i; return ma; } //// 本問題関連 typedef struct { int a, b, c; } T; T t[MAX];int N; int cmpb(const void *u, const void *v) { // b昇順, a昇順, c降順 int t; if (t = ((T *)u)->b - ((T *)v)->b) return t; if (t = ((T *)u)->a - ((T *)v)->a) return t; return ((T *)v)->c - ((T *)u)->c; } void compact() { int i, v, b; qsort(t, N, sizeof(T), cmpb); b = t[0].b, v = 1, t[0].b = v; for (i = 1; i < N; i++) { if (t[i].b == b) t[i].b = (t[i].a == t[i-1].a)? 0: v; else b = t[i].b, t[i].b = ++v; } } int cmp(const void *u, const void *v) { // a昇順, b降順 int t; if (t = ((T *)u)->a - ((T *)v)->a) return t; return ((T *)v)->b - ((T *)u)->b; } int main() { int i; N = in(); for (i = 0; i < N; i++) { t[i].a = in(), t[i].b = in(), t[i].c = in(); } compact(); // データ圧縮 qsort(t, N, sizeof(T), cmp); //for (i = 0; i < N; i++) printf("[%d] (%d,%d,%d)\n", i, t[i].a, t[i].b, t[i].c); bitn = N+1; for (i = 0; i < N; i++) if (t[i].b) update(t[i].b+1, maxv(t[i].b) + t[i].c); printf("%lld\n", maxv(N+1)); return 0; }