#include "fish.h"
#include <bits/stdc++.h>
typedef long long ll;
void Max(ll &x,ll y){if(x<y)x=y;}
ll max_weights(int n,int m,std::vector<int> X,std::vector<int> Y,std::vector<int> W)
{
	if(n>3000)
		return 0;
	constexpr int NN(3003);
	static ll sum[NN][NN];
	for(int i(0);i<m;++i)
		sum[X[i]+1][Y[i]+1]+=W[i];
	for(int i(1);i<=n;++i)
	for(int j(1);j<=n;++j)
		sum[i][j]+=sum[i][j-1];
	static ll dp[NN][2][NN];
	memset(dp,0xc0,sizeof(dp));
	dp[0][0][0]=0;
	for(int i(1);i<=n;++i)
	{
		Max(dp[i][0][0],dp[i-1][0][0]);
		Max(dp[i][0][0],dp[i-1][1][0]);
		for(int j(1);j<=n;++j)
		{
			for(int k(0);k<=j;++k)
				Max(dp[i][0][j],dp[i-1][0][k]+sum[i-1][j]-sum[i-1][k]);
		}
		
		for(int j(0);j<=n;++j)
		for(int k(j);k<=n;++k)
			Max(dp[i][1][j],dp[i-1][1][k]+sum[i][k]-sum[i][j]);
		
		for(int j(1);j<=n;++j)
			Max(dp[i][1][j],dp[i][0][j]);
		
	}
	ll ans(0);
	for(int i(0);i<=n;++i)
		Max(ans,dp[n][0][i]),Max(ans,dp[n][1][i]);
	return ans;
}