#include "fish.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int nx=3e3+5;
ll dp[nx][nx][2], qs[nx][nx], mx;
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
for (int i=0; i<M; i++) qs[X[i]+1][Y[i]+1]=W[i];
for (int i=1; i<=N; i++) for (int j=1; j<=N; j++) qs[i][j]+=qs[i][j-1];
for (int i=1; i<=N; i++)
{
vector<ll> mx1(nx), mx2(nx), mx4(nx);
for (int j=0; j<=N; j++) mx1[j]=max(j>0?mx1[j-1]:LLONG_MIN, dp[i-1][j][0]-qs[i-1][j]-qs[i][j]);
for (int j=N; j>=0; j--) mx2[j]=max(j<N?mx2[j+1]:LLONG_MIN, max(dp[i-1][j][0], dp[i-1][j][1]));
if (i>=2) for (int j=0; j<=N; j++) mx4[j]=max(j>0?mx4[j-1]:LLONG_MIN, max(dp[i-2][j][0], dp[i-2][j][1]));
for (int j=0; j<=N; j++)
{
dp[i][j][0]=max(dp[i][j][0], qs[i+1][j]+qs[i-1][j]+mx1[j]);
dp[i][j][1]=max(dp[i][j][1], qs[i+1][j]-qs[i][j]+mx2[j]);
if (i>=2) dp[i][j][0]=max(dp[i][j][0], qs[i+1][j]+mx4[j]);
mx=max({mx, dp[i][j][0], dp[i][j][1]});
}
}
return mx;
}
