#include<bits/stdc++.h>
#define MAXN 3007
using namespace std;
int n,m,maxx;
long long pref[MAXN][MAXN],dp[MAXN][MAXN][2];
bool li[MAXN][MAXN][2];
long long ff(int pos,int last,int flag){
if(pos==-1)return 0;
if(li[pos][last][flag])return dp[pos][last][flag];
li[pos][last][flag]=true;
for(int i=0;i<=last;i++){
dp[pos][last][flag]=max(dp[pos][last][flag],ff(pos-1,i,1)+pref[pos][last]-pref[pos][i]);
dp[pos][last][flag]=max(dp[pos][last][flag],ff(pos-1,i,0));
}
for(int i=last+1;i<=n;i++){
if(flag==0)dp[pos][last][flag]=max(dp[pos][last][flag],ff(pos-1,i,0)+pref[pos+1][i]-pref[pos+1][last]);
else dp[pos][last][flag]=max(dp[pos][last][flag],ff(pos-1,i,0));
}
return dp[pos][last][flag];
}
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];
}
for(int i=0;i<n;i++){
for(int f=1;f<=n;f++){
pref[i][f]=pref[i][f]+pref[i][f-1];
}
}
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";
}
*/
