daejeon2014l.cpp

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <limits.h>
#include <math.h>
#include <time.h>
#include <iostream>
#include <functional>
#include <numeric>
#include <algorithm>
#include <stack>
#include <queue>
#include <deque>
#include <vector>
#include <string>
#include <bitset>
#include <map>
#include <set>
using namespace std;
typedef long long lint;
typedef long double llf;
typedef pair<int, int> pi;

struct intv{
	int s, e, x;
}a[10005];

int n;
vector<int> gph[10005];
int dp1[10005], low[10005];
map<int, int> mp[10005];

int get(int x, int y){
	if(mp[x].find(y) != mp[x].end()) return mp[x][y];
	int ret = dp1[max(low[x], low[y])];
	auto t = upper_bound(gph[x].begin(), gph[x].end(), y);
	auto u = upper_bound(gph[y].begin(), gph[y].end(), x);
	if(t != gph[x].end()) ret = max(ret, get(x, *t) + a[*t].x - a[y].x);
	if(u != gph[y].end()) ret = max(ret, get(*u, y) + a[*u].x - a[x].x);
	t = lower_bound(gph[x].begin(), gph[x].end(), low[y]);
	u = lower_bound(gph[y].begin(), gph[y].end(), low[x]);
	if(t != gph[x].end()) ret = max(ret, get(x, *t) + a[*t].x);
	if(u != gph[y].end()) ret = max(ret, get(*u, y) + a[*u].x);
	return mp[x][y] = ret;
}

void solve(){
	cin >> n;
	for(int i=0; i<n; i++){
		cin >> a[i].s >> a[i].e >> a[i].x;
	}
	sort(a, a+n, [&](const intv &a, const intv &b){
		return pi(a.s, a.e) < pi(b.s, b.e);
	});
	for(int i=0; i<n; i++){
		low[i] = i+1;
		for(int j=i+1; j<n; j++){
			if(a[i].e >= a[j].s){
				gph[i].push_back(j);
				gph[j].push_back(i);
				low[i] = j+1;
			}
			else break;
		}
	}
	for(int i=0; i<n; i++){
		sort(gph[i].begin(), gph[i].end());
	}
	for(int i=n-1; i>=0; i--){
		dp1[i] = max(dp1[i+1], dp1[low[i]] + a[i].x);
		for(auto &j : gph[i]){
			get(i, j);
			if(i < j) dp1[i] = max(dp1[i], mp[i][j] + a[i].x + a[j].x);
		}
	}
	cout << dp1[0] << endl;
}

void clear(){
	for(int i=0; i<n; i++){
		gph[i].clear();
		mp[i].clear();
	}
	memset(dp1, 0, sizeof(dp1));
	memset(low, 0, sizeof(low));
}

int main(){
	int t;
	cin >> t;
	while(t--){
		solve();
		clear();
	}
}