#include <bits/stdc++.h>
#define pb push_back
#define fst first
#define snd second
#define fore(i,a,b) for(int i=a,pao=b;i<pao;++i)
#define SZ(x) ((int)x.size())
#define ALL(x) x.begin(),x.end()
#define mset(a,v) memset((a),(v),sizeof(a))
#define FIN ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
using namespace std;
typedef long long ll;
const int MAXN=1e5+5;
const ll INF=1e18;
set<ll>s[MAXN];
unordered_map<ll,ll>dp[MAXN][2];
unordered_map<ll,ll>a[MAXN],pref[MAXN];
void chmax(ll &a,ll b){
a=max(a,b);
}
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
fore(i,0,M){
X[i]++;Y[i]++;
a[X[i]][Y[i]]+=W[i];
s[X[i]-1].insert(Y[i]);
s[X[i]].insert(Y[i]);
s[X[i]+1].insert(Y[i]);
}
fore(i,0,N+1){
s[i].insert(0);
s[i].insert(N);
if(i){
ll sum=0;
for(auto x:s[i]){
sum+=a[i][x];
pref[i][x]=sum;
}
}
}
ll ans=-INF;
dp[0][1][0]=0;
fore(i,1,N+1){
map<ll,ll>prefMax,sufMax;
ll ndp=-INF;
for(auto x:s[i-1]){
chmax(ndp,dp[i-1][0][x]);
chmax(ndp,dp[i-1][1][x]);
}
ll best=-INF;
for(auto x:s[i-1]){
chmax(prefMax[x],best);
chmax(prefMax[x],dp[i-1][1][x]-pref[i-1][x]);
chmax(best,prefMax[x]);
}
best=-INF;
for(auto it=--s[i-1].end();;it--){
ll x=*it;
ll ant=max(dp[i-1][0][x],dp[i-1][1][x]);
auto jt=s[i].lower_bound(x);
jt--;
ll y=*jt;
chmax(sufMax[x],best);
chmax(sufMax[x],ant+pref[i][y]);
chmax(best,sufMax[x]);
if(it==s[i-1].begin())break;
}
for(auto x:s[i]){
if(x==0){
dp[i][0][x]=dp[i][1][x]=ndp;
}
auto it=s[i-1].upper_bound(x);
it--;
ll y=*it;
chmax(dp[i][1][x],pref[i-1][y]+prefMax[y]); //x >= y
chmax(dp[i][0][x],sufMax[y]-pref[i][x]); // x <= y
ans=max({ans,dp[i][1][x],dp[i][0][x]});
}
}
return ans;
}
