#include "fish.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
using namespace std;
typedef long long ll;
ll n,m;
struct date
{
ll poz,val;
};
vector<date> myy[100005];
ll dp[3][3005][3005],v[3005][3005];
bool comp(date a, date b)
{
return a.poz<b.poz;
}
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
n=N;
m=M;
for(int i=0;i<m;i++)
{
ll x=X[i];
ll y=Y[i];
ll w=W[i];
myy[x+1].push_back({y+1,w});
v[x+1][y+1]=w;
}
for(int i=1;i<=n;i++)
{
myy[i].push_back({0,0});
myy[i].push_back({n+1,0});
sort(myy[i].begin(),myy[i].end(),comp);
}
ll ans=0;
for(int i=2;i<=n;i++)
{
// neutru
ll suma=0;
for(ll p=0;p<=n;p++)
{
suma+=v[i][p];
for(ll p1=p;p1<=n;p1++)
dp[0][i][p]=max(dp[0][i][p],suma+max(dp[1][i-1][p1],dp[2][i-1][p1]));
if(p==0)
{
for(int p1=0;p1<=p;p1++)
dp[0][i][p]=max(dp[0][i][p],dp[0][i-1][p1]);
}
ans=max(ans,dp[0][i][p]);
}
// cresc
for(ll p=0;p<=n;p++)
{
ll s1=0;
for(ll j=0;j<=p;j++)
s1+=v[i-1][j];
ll s2=0;
for(ll j=0;j<=n;j++)
{
s2+=v[i-1][j];
dp[1][i][p]=max(dp[1][i][p],max(0LL,s1-s2)+max(dp[0][i-1][j],dp[1][i-1][j]));
}
ans=max(ans,dp[1][i][p]);
}
// desc
for(ll p=0;p<=n;p++)
{
ll s2=0;
for(ll j=0;j<=p;j++)
s2+=v[i][j];
ll s1=0;
for(ll j=0;j<=n;j++)
{
s1+=v[i][j];
dp[2][i][p]=max(dp[2][i][p],max(0LL,s1-s2+max(dp[1][i-1][j],dp[2][i-1][j])));
}
ans=max(ans,dp[2][i][p]);
}
}
return ans;
}
