#include<bits/stdc++.h>
#pragma GCC optimize ("O3")
#pragma GCC target ("sse4")
#define MAXN 3007
using namespace std;
int n,m,maxx;
long long pref[MAXN][MAXN];
bool in[MAXN][MAXN];
vector<long long> dp[MAXN][2];
vector<bool> li[MAXN][2];
vector< pair<int,int> > good[MAXN];
long long sum(int pos,int l,int r){
return pref[pos][r]-pref[pos][l];
}
long long ff(int pos,int last,int flag){
if(pos==-1)return 0;
if(li[pos][flag][last])return dp[pos][flag][last];
li[pos][flag][last]=true;
for(int i=0;i<good[pos].size() and good[pos][i].first<=good[pos+1][last].first;i++){
dp[pos][flag][last]=max(dp[pos][flag][last],ff(pos-1,i,1)+sum(pos,good[pos][i].first,good[pos+1][last].first));
dp[pos][flag][last]=max(dp[pos][flag][last],ff(pos-1,i,0));
}
for(int i=good[pos].size()-1;i>=0 and good[pos][i].first>good[pos+1][last].first;i--){
if(flag==0)dp[pos][flag][last]=max(dp[pos][flag][last],ff(pos-1,i,0)+sum(pos+1,good[pos+1][last].first,good[pos][i].first));
else dp[pos][flag][last]=max(dp[pos][flag][last],ff(pos-1,i,0));
}
return dp[pos][flag][last];
}
long long max_weights(int N, int M,vector<int> X,vector<int> Y,vector<int> W){
n=N; m=M;
for(int i=0;i<m;i++){
pref[X[i]][Y[i]+1]+=W[i];
if(X[i]>0 and !in[X[i]-1][Y[i]+1]){
good[X[i]-1].push_back({Y[i]+1,W[i]});
in[X[i]-1][Y[i]+1]=true;
}
if(X[i]<n-1 and !in[X[i]+1][Y[i]+1]){
good[X[i]+1].push_back({Y[i]+1,W[i]});
in[X[i]+1][Y[i]+1]=true;
}
}
for(int i=0;i<n;i++){
for(int f=1;f<=n;f++){
pref[i][f]+=pref[i][f-1];
}
}
for(int i=0;i<=n;i++){
good[i].push_back({0,0});
sort(good[i].begin(),good[i].end());
dp[i][0].resize(good[i+1].size()+5);
dp[i][1].resize(good[i+1].size()+5);
li[i][0].resize(good[i+1].size()+5);
li[i][1].resize(good[i+1].size()+5);
}
return ff(n-1,0,0);
}
/*
int main(){
cout<<max_weights(5, 4, {0, 1, 4, 3}, {2, 1, 4, 3}, {5, 2, 1, 3})<<"\n";
}
*/
