#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
struct cell
{
long long int a,b,c;
};
long long int mat[3005][3005],col[3005][3005],n,m;
long long int otg,dp[3005][3005],mdp[3005],rdp[3005][3005],sdp[3005][3005],ultdp[3005];
cell a[300005];
void make_dp()
{
long long int ma1=0,ma2=0,use1=0,use2=0,l1=0,l2=0;
for(int j=1;j<=n;j++)
{
ma1=0;
ma2=0;
use1=mdp[j-1];
use2=mdp[j-2];
l1=0;
l2=0;
for(int i=1;i<=n;i++)
{
ma1+=mat[i][j-1];
ma1=max(ma1,sdp[i][j-1]);
if(j>=2)
{
ma2+=mat[i][j-1];
ma2=max(ma2,rdp[i][j-2]);
}
if(!l1)use1-=mat[i][j];
if(ma1>=use1)
{
use1=ma1;
l1=1;
}
if(ma2>=use2)
{
use2=ma2;
}
if(j>=3)dp[i][j]=ultdp[j-3]+col[i][j-1]+col[i][j+1];
else dp[i][j]=col[i][j-1]+col[i][j+1];
dp[i][j]=max(dp[i][j],use1+col[i][j+1]);
dp[i][j]=max(dp[i][j],use2+col[i][j+1]);
sdp[i][j]=max(ma1,rdp[i][j-1]);
sdp[i][j]=max(sdp[i][j],use2);
sdp[i][j]=max(sdp[i][j],ultdp[j-3]+col[i][j-1]);
rdp[i][j]=dp[i][j]-col[i][j+1];
mdp[j]=max(mdp[j],dp[i][j]);
otg=max(otg,dp[i][j]);
}
ultdp[j]=max(ultdp[j],mdp[j]);
}
//cout<<endl;
for(int i=n;i>=1;i--)
{
for(int j=1;j<=n;j++)
{
//cout<<dp[i][j]<<" ";
}
//cout<<endl;
}
}
long long int max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W)
{
n=N;
m=M;
for(int i=1;i<=m;i++)
{
a[i].a=Y[i-1]+1;
a[i].b=X[i-1]+1;
a[i].c=W[i-1];
mat[a[i].a][a[i].b]=a[i].c;
}
for(int i=1;i<=n;i++)
{
for(int j=1;j<=n;j++)
{
col[i][j]=col[i-1][j]+mat[i][j];
}
}
for(int i=n;i>=1;i--)
{
for(int j=1;j<=n;j++)
{
//cout<<mat[i][j]<<" ";
}
//cout<<endl;
}
//cout<<endl;
make_dp();
return otg;
}
