/**
* بسم الله الرحمن الرحيم *
﴾ رَبِّ اشْرَحْ لِي صَدْرِي * وَيَسِّرْ لِي أَمْرِي * وَاحْلُلْ عُقْدَةً مِّن لِّسَانِي * يَفْقَهُوا قَوْلِي ﴿
*/
/// author : "ASGA"
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
ll max_weights(int N,int M,vector<int>X,vector<int>Y,vector<int>W){
int n=1,m=1;
for(int i=0;i<M;i++){n=max(n,X[i]+5);m=max(m,Y[i]+5);}
n=min(n,N);m=min(m,N);
if(n*m>1e7){
int spt=1;
for(int&i:X)spt&=(i%2==0);
if(spt)return accumulate(W.begin(),W.end(),0LL);
}
vector<vector<ll>>w(n,vector<ll>(m,0));
for(int i=0;i<M;i++){
w[X[i]][Y[i]]=W[i];
}
vector<vector<ll>>d(n,vector<ll>(m+1,0));
vector<ll>mx(n,0);
vector<ll>d1(m+1,0),d2(m+1,0);
for(int i=1;i<n;i++){
vector<ll>p(m+1,0);
ll s=accumulate(w[i].begin(),w[i].end(),0LL);
for(int j=m-1;j>=0;j--){
p[j]=max(p[j+1],d[i-1][j+1]+s);
s-=w[i][j];
}
s=0;
for(int j=m-1;j>=0;j--){
s+=w[i-1][j];
d1[j]+=s;
}
for(int j=1;j<=m;j++)d1[j]=max(d1[j],d1[j-1]);
s=0;
ll ss=accumulate(w[i-1].begin(),w[i-1].end(),0LL);
ll sss=0;
for(int j=0;j<=m;j++){
ll&r=d[i][j];
r=d1[j]-ss;
if(i>1)r=max(r,mx[i-2]+sss);
d2[j]=r;
r=max(p[j]-s,r);
if(j<m){s+=w[i][j];ss-=w[i-1][j];sss+=w[i-1][j];}
r=max(r,mx[i-1]);
mx[i]=max(mx[i],r);
}
d1=d2;
}
return *max_element(d.back().begin(),d.back().end());
}
