#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
vector<pair<int,long long> > arr[100005];
long long qry(int col,int height){ //prefixsum of col to height
if (arr[col].empty()) return 0;
pair<int,long long> lol=mp(height,1e18);
int pos=upper_bound(arr[col].begin(),arr[col].end(),lol)-arr[col].begin();
pos--;
return arr[col][pos].second;
}
vector<long long> dp1[100005]; //col,height,increasing
vector<long long> dp2[100005]; //col,height,decreasing
vector<long long> whack[100005];
long long max_weights(int n,int m,vector<int> x,vector<int> y,vector<int> w){
for (int i=0;i<m;i++){
x[i]++;
y[i]++;
arr[x[i]].pb(mp(y[i],w[i]));
}
for (int i=1;i<=n;i++){
arr[i].pb(mp(0,0));
sort(arr[i].begin(),arr[i].end());
for (int j=1;j<(int)arr[i].size();j++){
arr[i][j].second+=arr[i][j-1].second;
}
for (auto j:arr[i]){
whack[i].pb(j.first);
whack[i+1].pb(j.first);
whack[i-1].pb(j.first);
}
}
for (int i=0;i<=n;i++){
sort(whack[i].begin(),whack[i].end());
whack[i].erase(unique(whack[i].begin(),whack[i].end()),whack[i].end());
for (int j=0;j<(int) whack[i].size();j++){
dp1[i].pb(0);
dp2[i].pb(0);
}
}
for (int i=1;i<=n;i++){ //col
long long maxi=0,id=0;
for (int j=0;j<(int)whack[i].size();j++){
int k=whack[i][j];
while (id<(int)whack[i-1].size() && whack[i-1][id]<=k){
maxi=max(maxi,dp1[i-1][id]-qry(i,whack[i-1][id])-qry(i-1,whack[i-1][id]));
id++;
}
dp1[i][j]=maxi+qry(i-1,k)+qry(i+1,k);
}
if (i>=2){
maxi=0;
id=0;
for (int j=0;j<(int)whack[i].size();j++){
int k=whack[i][j];
while (id<(int)whack[i-2].size() && whack[i-2][id]<=k){
maxi=max(maxi,dp2[i-2][id]-qry(i-1,whack[i-2][id]));
id++;
}
dp1[i][j]=max(dp1[i][j],maxi+qry(i-1,k)+qry(i+1,k));
}
maxi=0;
id=whack[i-2].size()-1;
for (int j=whack[i].size()-1;j>=0;j--){
int k=whack[i][j];
while (id>=0 && whack[i-2][id]>=k){
maxi=max(maxi,dp2[i-2][id]);
id--;
}
dp1[i][j]=max(dp1[i][j],maxi+qry(i+1,k));
}
}
maxi=0;
id=whack[i-1].size()-1;
for (int j=whack[i].size()-1;j>=0;j--){
int k=whack[i][j];
while (id>=0 && whack[i-1][id]>=k){
maxi=max(maxi,dp2[i-1][id]);
id--;
}
dp2[i][j]=maxi+qry(i+1,k)-qry(i,k);
}
for (int j=0;j<(int)whack[i].size();j++){
dp2[i][j]=max(dp2[i][j],dp1[i][j]);
}
}
long long ans=0;
for (int j=0;j<(int)dp2[n].size();j++){
ans=max(ans,dp2[n][j]);
}
return ans;
}
