#include <bits/stdc++.h>
//#include "fish.h"
using namespace std;
#define pb push_back
#define mp make_pair
long long dp[3005][3005][2]; //col,height,increasing/decreasing
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;
}
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 i=1;i<=n;i++){ //col
for (int j=0;j<=n;j++){ //col height
dp[i][j][0]=-1e18;
dp[i][j][1]=-1e18;
}
long long maxi=0;
for (int j=0;j<=n;j++){
maxi=max(maxi,dp[i-1][j][0]-qry(i,j)-qry(i-1,j));
if (i>=2){
maxi=max(maxi,dp[i-2][j][1]-qry(i-1,j));
}
dp[i][j][0]=maxi+qry(i-1,j)+qry(i+1,j);
}
maxi=0;
if (i>=2){
for (int j=n;j>=0;j--){
maxi=max(maxi,dp[i-2][j][1]);
dp[i][j][0]=max(dp[i][j][0],maxi+qry(i+1,j));
}
}
maxi=0;
for (int j=n;j>=0;j--){
maxi=max(maxi,dp[i-1][j][1]);
dp[i][j][1]=maxi+qry(i+1,j)-qry(i,j);
}
for (int j=0;j<=n;j++){
dp[i][j][1]=max(dp[i][j][1],dp[i][j][0]);
}
}
long long ans=0;
for (int j=0;j<=n;j++){
ans=max(ans,dp[n][j][1]);
}
return ans;
}
