test

/************************************************
*Author        :  demonlover
*Created Time  :  2022.11.17.08:43
*Problem       :  3002
*The best era, prosperous times.
*Not only your Fiesta, but also mine.
************************************************/
#include <iostream>
#include <cstdio>
#include <cstring>
#include <bitset>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pii;
template <typename T>
inline bool read(T &x) {
	int f = 1,c = getchar();x = 0;
	while (!isdigit(c)) {if (c == 45)f = -1;c = getchar();}
	while (isdigit(c))x = (x<<3)+(x<<1)+(c^48),c = getchar();
	return x *= f,true;
}
template <typename T,typename... Args>
inline bool read(T &x,Args &...args) {
	return read(x) && read(args...);
}

namespace run {
	const int maxn = 5e2+10;
	int a[maxn],c[maxn],val[maxn];
	int suf[maxn];
	int n,ans = 1e9;
	bitset<maxn> *f[maxn][maxn],g[2][maxn],ls[maxn],rs[maxn];
	inline bool main() {
		read(n);
		for (int i = 1;i <= n;++i)read(c[i],a[i],val[i]);
		for (int i = 0;i <= n;++i)for (int j = 1;j <= n;++j)
			if (!i || c[i] == c[j] || a[i] == a[j])ls[j].set(i),rs[i].set(j);
		n += 3;
		for (int i = 1;i <= n;++i)for (int j = 1;j <= i;++j)f[i][j] = new bitset<maxn>;
		for (int i = n;i >= 1;--i)suf[i] = suf[i+1]+val[i];
		g[0][1][0] = 1;
		for (int i = 3,now = 0;i <= n;++i,now ^= 1) {
			for (int j = 1;j <= i;++j)g[now^1][j].reset();
			for (int j = 0;j <= i;++j)if (g[now][j].any())ans = min(ans,suf[i-1]+val[j]);
			if (rs[i-1][i])for (int j = 1;j <= i;++j)*f[i+1][j] = *f[i][j];
			for (int j = 1;j <= i;++j)g[now^1][j] = rs[i-1]&(*f[i][j]);
			for (int j = 1;j <= i;++j)if ((g[now][j]&ls[j]).any())g[now^1][i-1].set(j);
			for (int j = 1;j <= i;++j)if ((g[now][j]&ls[i]).any())f[i+1][i-1]->set(j);
		}
		for (int i = 1;i < n;++i) {
			bitset<maxn> A,B;
			for (int j = n;j >= max(3,i);--j) {
				B = (*f[j][i])&(~A);
				for (int k = B._Find_first();k <= n;k = B._Find_next(k))ans = min(ans,val[i]+val[k]+suf[j]);
				A |= B;
			}
		}
		printf("%d\n",suf[1]-ans);
		cerr<<1.0*clock()/CLOCKS_PER_SEC<<"\n";
		return 0;
	}
}

#define demonlover
int main() {
#ifdef demonlover
	freopen("3002.in","r",stdin);
	freopen("3002.out","w",stdout);
#endif
	return run :: main();
}