#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vll vector<ll>
#define all(x) begin(x),end(x)
const int N=1e5+10;
vll pre[N];
ll sz[N];
vll dp[N][3];
vll possible[N];
vector<pair<ll,ll>> values[N];
ll solve(ll&n,ll&m,vll&x,vll&y,vll&w)
{
ll ans=0;
for(int j=0;j<m;j++)
{
values[x[j]].push_back({y[j]+1,w[j]});
possible[x[j]].push_back(y[j]+1);
possible[x[j]+1].push_back(y[j]+1);
if(x[j]>0)
possible[x[j]-1].push_back(y[j]+1);
}
for(int i=0;i<=n;i++)
{
possible[i].push_back(0);
possible[i].push_back(n);
sort(begin(possible[i]),end(possible[i]));
sort(begin(values[i]),end(values[i]));
sz[i]=possible[i].size();
pre[i].resize(sz[i]+1,0);
ll sm=0;
int pp=0;
int rp=0;
for(auto&j:possible[i])
{
while(pp<values[i].size() and values[i][pp].first<=j)
{
sm+=values[i][pp].second;
pp++;
}
pre[i][rp]=sm;
rp++;
}
dp[i][0].resize(sz[i]+1,0);
dp[i][1].resize(sz[i]+1,0);
}
// for(int i=0;i<n;i++)
// for(int j=0;j<=n;j++)
// for(int k=0;k<2;k++)
// dp[i][j][k]=0;
for(int i=1;i<n;i++)
{
// ll sum=0;
ll mx1=-2e18;
ll mx2=-2e18;
ll mx11=0,mx22=0;
for(int k=0;k<sz[i];k++)
{
int hp=possible[i][k];
mx11=max(mx11,dp[i-1][0][k]);
auto index=lower_bound(all(possible[i-1]),hp)-begin(possible[i-1]);
mx1=max(mx1,dp[i-1][0][k]-pre[i-1][index]);
}
for(int k=0;k<sz[i];k++)
{
int hp=possible[i][k];
mx11=max(mx11,dp[i-1][1][k]);
auto index=lower_bound(all(possible[i]),hp)-begin(possible[i]);
mx1=max(mx1,dp[i-1][1][k]+pre[i][index]);
}
int pp=0;
for(auto&h:possible[i])
{
auto index=lower_bound(all(possible[i-1]),h)-begin(possible[i-1]);
dp[i][0][pp]=max(dp[i][0][pp],mx1+pre[i-1][index]);
dp[i][1][pp]=max(dp[i][1][pp],mx1+pre[i-1][index]);
dp[i][1][pp]=max(dp[i][1][pp],mx2-pre[i][pp]);
dp[i][0][pp]=max(dp[i][0][pp],mx11);
dp[i][0][pp]=max(dp[i][0][pp],mx22);
dp[i][1][pp]=max(dp[i][1][pp],mx11);
dp[i][1][pp]=max(dp[i][1][pp],mx22);
pp++;
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<sz[i];j++)
{
ans=max(ans,dp[i][0][j]);
ans=max(ans,dp[i][1][j]);
}
}
return ans;
}
ll subtask2(ll&n,ll&m,vll&x,vll&y,vll&w)
{
ll ans=0;
ll val[2][n]={0};
for(int i=0;i<2;i++)
{
for(int j=0;j<n;j++)
{
val[i][j]=0;
}
}
ll sum1=0,sum0=0;
for(int j=0;j<m;j++)
{
val[x[j]][y[j]]+=w[j];
if(x[j]==1)
{
sum1+=w[j];
}
else
{
sum0+=w[j];
}
}
ans=max(sum0,sum1);
ll taken=0;
ll cur=0;
for(int j=0;j<n;j++)
{
cur+=val[0][j];
taken+=val[1][j];
ans=max(ans,cur);
if(n>2)
ans=max(ans,cur+sum1-taken);
}
return ans;
}
ll subtask3(ll&n,ll&m,vll&x,vll&y,vll&w)
{
ll ans=0;
ll val[n+1];
for(int i=0;i<n;i++)val[i]=0;
for(int j=0;j<m;j++)val[x[j]]+=w[j];
ll dp[n+1][3][3];
for(int i=0;i<n;i++)
for(int j=0;j<2;j++)
for(int k=0;k<2;k++)
dp[i][j][k]=0;
for(int i=1;i<n;i++)
{
// wall not at i
dp[i][0][0]=max(max(dp[i-1][0][0],dp[i-1][0][1]),dp[i-1][1][0]);
dp[i][0][1]=max(max(dp[i-1][0][0],dp[i-1][0][1]),dp[i-1][1][0]+val[i]);
dp[i][1][0]=max(max(dp[i-1][0][1],dp[i-1][0][0]+val[i-1]),dp[i-1][1][0]);
}
for(int i=0;i<n;i++)
{
ans=max({ans,dp[i][0][0],dp[i][0][1],dp[i][1][0],dp[i][1][1]});
}
return ans;
}
const int N2=3e3+1;
ll val1[N2][N2],pre1[N2][N2];
ll dp1[N2][N2][3];
ll solver(ll&n,ll&m,vll&x,vll&y,vll&w)
{
ll ans=0;
for(int i=0;i<n;i++)for(int j=0;j<=n;j++)val1[i][j]=pre1[i][j]=0;
for(int j=0;j<m;j++)val1[x[j]][y[j]+1]+=w[j];
for(int i=0;i<=n;i++)
{
pre1[i][0]=val1[i][0];
for(int j=1;j<=n;j++)
pre1[i][j]=pre1[i][j-1]+val1[i][j];
}
for(int i=0;i<n;i++)
for(int j=0;j<=n;j++)
for(int k=0;k<2;k++)
dp1[i][j][k]=0;
for(int i=1;i<n;i++)
{
// ll sum=0;
ll mx1=-2e18;
ll mx2=-2e18;
ll mx11=0,mx22=0;
for(int hp=0;hp<=n;hp++)
{
mx11=max(mx11,dp1[i-1][hp][0]);
mx22=max(mx22,dp1[i-1][hp][1]);
mx1=max(mx1,dp1[i-1][hp][0]-pre1[i-1][hp]);
mx2=max(mx2,dp1[i-1][hp][1]+pre1[i][hp]);
}
for(int h=0;h<=n;h++)
{
dp1[i][h][0]=max(dp1[i][h][0],mx1+pre1[i-1][h]);
dp1[i][h][1]=max(dp1[i][h][1],mx1+pre1[i-1][h]);
dp1[i][h][1]=max(dp1[i][h][1],mx2-pre1[i][h]);
dp1[i][h][0]=max(dp1[i][h][0],mx11);
dp1[i][h][0]=max(dp1[i][h][0],mx22);
dp1[i][h][1]=max(dp1[i][h][1],mx11);
dp1[i][h][1]=max(dp1[i][h][1],mx22);
}
}
for(int i=0;i<n;i++)
{
for(int h=0;h<=n;h++)
{
ans=max(ans,dp1[i][h][0]);
ans=max(ans,dp1[i][h][1]);
}
}
return ans;
}
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,std::vector<int> W)
{
ll n=N,m=M,ans=0;
vector<ll> x(all(X)),y(all(Y)),w(all(W));
ll mx_x=*max_element(all(x));
ll mx_y=*max_element(all(y));
if(mx_x<=1)
return subtask2(n,m,x,y,w);
set<ll> posmod;
for(auto i:x)
{
posmod.insert(i%2);
}
if(posmod.size()==1 or mx_y==0)
return subtask3(n,m,x,y,w);
if(n<=3000)
{
return solver(n,m,x,y,w);
}
return solve(n,m,x,y,w);
}
