#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e5+5;
const ll inf=1e18;
int n,m;
vector<vector<ll>> w;
vector<vector<vector<ll>>> dp;
ll suff[N];
ll val[N];
long long max_weights(int _n,int _m,vector<int> X,vector<int> Y,vector<int> W) {
n=_n,m=_m;
int mxy=0,mxx=0;
for(auto x:X)mxx=max(mxx,x+1);
for(auto x:Y)mxy=max(mxy,x+1);
n=min(n,mxx+1);
w=vector<vector<ll>>(n+5,vector<ll>(mxy+5));
dp=vector<vector<vector<ll>>>(n+5,vector<vector<ll>>(mxy+5,vector<ll>(2)));
for(int i=0;i<m;i++)w[X[i]+1][Y[i]+1]=W[i];
for(int i=1;i<=n;i++)for(int j=1;j<=mxy;j++)w[i][j]+=w[i][j-1];
for(int i=1;i<=n;i++)for(int j=0;j<=mxy;j++)dp[i][j][0]=dp[i][j][1]=-inf;
for(int i=1;i<=n;i++){
if(i>=2)for(int j=mxy;j>=0;j--)suff[j]=max(suff[j+1],dp[i-2][j][1]);
ll tmp=-inf,tmp2=-inf;
for(int j=0;j<=mxy;j++){
tmp=max(tmp,dp[i-1][j][0]-w[i][j]-w[i-1][j]);
dp[i][j][0]=w[i-1][j]+tmp+w[i+1][j];
if(i>=2){
tmp2=max(tmp2,dp[i-2][j][0]-w[i-1][j]);
dp[i][j][0]=max(dp[i][j][0],w[i-1][j]+tmp+w[i+1][j]);
dp[i][j][0]=max(dp[i][j][0],suff[j]+w[i+1][j]);
}
}
tmp=-inf;
for(int j=mxy;j>=0;j--){
tmp=max(tmp,dp[i-1][j][1]);
dp[i][j][1]=tmp-w[i][j]+w[i+1][j];
dp[i][j][1]=max(dp[i][j][1],dp[i][j][0]);
}
}
ll ans=0;
for(int i=0;i<=mxy;i++)ans=max(ans,dp[n][i][1]);
return ans;
}
