#include "fish.h"
#ifdef LOCAL
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define iint signed
// #define ll long long
#define REP(i,n) for(int i=0;i<n;i++)
#define REP1(i,n) for(int i=1;i<=n;i++)
#define RREP(i,n) for(int i=(n)-1;i>=0;i--)
#define RREP1(i,n) for(int i=(n);i>=1;i--)
#define Vi vector<int>
#define pii pair<int,int>
#define Vpii vector<pii>
#define f first
#define s second
#define chmin(x,y) x=min(x,y)
#define chmax(x,y) x=max(x,y)
#define Graph vector<Vi>
#define Graphw vector<Vpii>
#define SZ(x) ((int)(x.size()))
#define ALL(x) x.begin(),x.end()
#ifdef LOCAL
#define entr cerr<<endl;
#define op(x) cerr<<(#x)<<"="<<(x)<<", ";
#define ope(x) cerr<<(#x)<<"="<<(x)<<endl;
#define oparr(x) { cerr<<(#x)<<": ";for(auto __:x) cerr<<__<<" ";cerr<<"size="<<SZ(x)<<endl; }
#else
#define entr ;
#define op(x) ;
#define ope(x) ;
#define oparr(x) {}
#endif
template<typename S> ostream& operator<<(ostream& os,vector<S> v) {
for(auto __:v) os<<__<<" ";
return os<<endl;
}
struct BIT {
iint n;
Vi b;
void init(int _n) {
n=_n;
b=Vi(n+1);
}
void ud(iint u,int v) {
for(;u<=n;u+=u&-u) chmax(b[u],v);
}
int qu(iint u) {
int an=0;
for(;u>0;u-=u&-u) chmax(an,b[u]);
return an;
}
};
long long max_weights(iint N, iint M, std::vector<iint> X, std::vector<iint> Y,
std::vector<iint> W) {
;
int n=N,m=M;
struct S {
int x,y,w;
};
vector<S> a(m+1);
REP1(i,m) a[i]={X[i-1]+1,Y[i-1]+1,W[i-1]};
auto ai=a,ad=a;
REP1(i,m) ad[i].y=n-ad[i].y+1;
sort(1+ALL(ai),[&](S a,S b) { return a.x==b.x?a.y<b.y:a.x<b.x; });
sort(1+ALL(ad),[&](S a,S b) { return a.x==b.x?a.y<b.y:a.x<b.x; });
vector<Vi> ci(n+1,Vi(n+1)),cd(n+1,Vi(n+1));
REP1(l,n) {
int st=m+1;
REP1(i,m) if(ai[i].x>=l) {
st=i;
break;
}
int it=st;
BIT bit;
bit.init(n);
int mx=0;
for(int r=l;r<=n;r++) {
while(it<=m&&ai[it].x==r) {
int y=ai[it].y,w=ai[it].w;
it++;
int ret=bit.qu(y-1);
bit.ud(y,ret+w);
chmax(mx,ret+w);
}
ci[l][r]=mx;
}
}
REP1(l,n) {
int st=m+1;
REP1(i,m) if(ad[i].x>=l) {
st=i;
break;
}
int it=st;
BIT bit;
bit.init(n);
int mx=0;
for(int r=l;r<=n;r++) {
while(it<=m&&ad[it].x==r) {
int y=ad[it].y,w=ad[it].w;
it++;
int ret=bit.qu(y-1);
bit.ud(y,ret+w);
chmax(mx,ret+w);
}
cd[l][r]=mx;
}
}
oparr(ci)oparr(cd)
Vi dp0(n+1),dp1(n+1);
REP1(i,n) {
REP1(j,i-1) chmax(dp0[i],dp1[j]+cd[j+1][i]);
if(i>1)chmax(dp1[i],dp1[i-2]+ci[i-1][i-1]);
REP(j,i-1) chmax(dp1[i],dp0[j]+ci[j+1][i-1]);
}
int an=max(dp0[n],dp1[n]);
oparr(dp0)oparr(dp1)
return an;
}
