#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 N(1e5+5),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[2][2][N];
	auto *pre(dp[0]),*now(dp[1]);
	memset(dp,0xc0,sizeof(dp));
	pre[0][0]=0;
	for(int i(1);i<=n;++i)
	{
		memset(now,0,sizeof(dp[0]));
		Max(now[0][0],pre[0][0]);
		Max(now[0][0],pre[1][0]);
		ll v;
		v=0xc0c0c0c0c0c0c0c0;
		for(int j(0);j<=n;++j)
		{
			Max(v,pre[0][j]-sum[i-1][j]);
			if(!j||sum[i-1][j]!=sum[i-1][j-1]||sum[i][j]!=sum[i][j-1]
				 ||sum[i-1][j]!=sum[i-1][j+1]||sum[i][j]!=sum[i][j+1])
				Max(now[0][j],sum[i-1][j]+v);
		}
		for(int j(1);j<=n;++j)
			if(!j||sum[i-1][j]!=sum[i-1][j-1]||sum[i][j]!=sum[i][j-1]
				 ||sum[i-1][j]!=sum[i-1][j+1]||sum[i][j]!=sum[i][j+1])
			Max(now[0][j],pre[1][0]);
		v=0xc0c0c0c0c0c0c0c0;
		for(int j(n);~j;--j)
		{
			Max(v,pre[1][j]+sum[i][j]);
			if(!j||sum[i-1][j]!=sum[i-1][j-1]||sum[i][j]!=sum[i][j-1]
				 ||sum[i-1][j]!=sum[i-1][j+1]||sum[i][j]!=sum[i][j+1])
				Max(now[1][j],v-sum[i][j]);
		}
		for(int k(0);k<=n;++k)
			Max(now[0][0],pre[1][k]);
		for(int j(1);j<=n;++j)
			if(!j||sum[i-1][j]!=sum[i-1][j-1]||sum[i][j]!=sum[i][j-1]
				 ||sum[i-1][j]!=sum[i-1][j+1]||sum[i][j]!=sum[i][j+1])
			Max(now[1][j],now[0][j]);
		std::swap(pre,now);
	}
	ll ans(0);
	for(int i(0);i<=n;++i)
		Max(ans,pre[0][i]),Max(ans,pre[1][i]);
	return ans;
}