#include "fish.h"
#include <bits/stdc++.h>
#define MX mx[i][idx][b]
#define int long long
using namespace std;
const int INF=1e18;
vector <int> v[100001];
vector <pair <int, int>> s[100001],mx[100002][4][2];
int n,m,x,y,res;
void update(int pos, int val, int i, int idx){
mx[pos][idx][0].push_back({i,val});
mx[pos][idx][1].push_back({n-i-1,val});
}
int get(int pos, int i, int idx, int b){
if (b)
pos=n-pos-1;
int p=upper_bound(MX.begin(),MX.end(),make_pair(pos,INF))-MX.begin()-1;
return (p<0?-INF:MX[p].second);
}
int sum(int i, int j){
if (i<0)
return 0;
return s[i][upper_bound(s[i].begin(),s[i].end(),make_pair(j,INF))-s[i].begin()-1].second;
}
int max_weights(int32_t N, int32_t M, vector <int32_t> X, vector <int32_t> Y, vector <int32_t> W){
n=N;
for (int i=0;i<M;i++){
s[X[i]].push_back({Y[i],W[i]});
if (X[i])
v[X[i]-1].push_back(Y[i]);
if (X[i]<N-1)
v[X[i]+1].push_back(Y[i]);
}
for (int i=0;i<n;i++){
v[i].push_back(-1);
sort(v[i].begin(),v[i].end());
v[i].resize(unique(v[i].begin(),v[i].end())-v[i].begin());
s[i].push_back({-1,0});
sort(s[i].begin(),s[i].end());
for (int j=1;j<s[i].size();j++)
s[i][j].second+=s[i][j-1].second;
}
for (int i:v[n-1]){
update(n,0,i,0);
update(n,0,i,1);
update(n,-sum(n-1,i),i,2);
update(n,sum(n-2,i),i,3);
}
for (int i=n-1;i>=0;i--){
for (int j=0;j<4;j++){
reverse(mx[i+1][j][1].begin(),mx[i+1][j][1].end());
for (int k=0;k<2;k++)
for (int l=1;l<mx[i+1][j][k].size();l++)
mx[i+1][j][k][l].second=max(mx[i+1][j][k][l].second,mx[i+1][j][k][l-1].second);
}
for (int j:v[i-1]){
x=max(max(get(j-1,i+1,2,0)+sum(i,j),get(j-1,i+1,1,0)),get(j,i+1,1,1));
y=max(max(get(j-1,i+1,2,0)+sum(i,j),get(j-1,i+1,1,0)),get(j,i+1,3,1)-sum(i-1,j));
res=max(res,max(x,y));
update(i,x,j,0);
update(i,y,j,1);
update(i,x-sum(i-1,j),j,2);
update(i,max(x,y)+sum(i-2,j),j,3);
}
}
return res;
}
