#include <bits/stdc++.h>
//#include "fish.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 (int j=0;j<=n;j++){
dp1[0].pb(0);
dp2[0].pb(0);
whack[0].pb(j);
}
for (int i=1;i<=n;i++){
for (int j=0;j<=n;j++){
dp1[i].pb(-1e18);
dp2[i].pb(-1e18);
whack[i].pb(j);
}
}
for (int i=1;i<=n;i++){ //col
long long maxi=0;
for (int j=0;j<=n;j++){
maxi=max(maxi,dp1[i-1][j]-qry(i,j)-qry(i-1,j));
if (i>=2){
maxi=max(maxi,dp2[i-2][j]-qry(i-1,j));
}
dp1[i][j]=maxi+qry(i-1,j)+qry(i+1,j);
}
maxi=0;
if (i>=2){
for (int j=n;j>=0;j--){
maxi=max(maxi,dp2[i-2][j]);
dp1[i][j]=max(dp1[i][j],maxi+qry(i+1,j));
}
}
maxi=0;
for (int j=n;j>=0;j--){
maxi=max(maxi,dp2[i-1][j]);
dp2[i][j]=maxi+qry(i+1,j)-qry(i,j);
}
for (int j=0;j<=n;j++){
dp2[i][j]=max(dp2[i][j],dp1[i][j]);
}
}
long long ans=0;
for (int j=0;j<=n;j++){
ans=max(ans,dp2[n][j]);
}
return ans;
}
