#include "bits/stdc++.h"
#include "fish.h"
//#define int64_t long long
#define all(v) v.begin() , v.end()
#define sz(a) (int64_t)a.size()
using namespace std;
const int64_t INF = 1e15;
long long max_weights(int N, int M, vector<int> X, vector<int> Y,vector<int> W){
int64_t n,m,ans=0;
n=N,m=M;
vector<array<int64_t,3>> ar(m);
for(int64_t i=0;i<m;i++){
ar[i][0]=X[i]+1;
ar[i][1]=Y[i]+1;
ar[i][2]=W[i];
}
vector<int64_t> consider[n+5];
vector<array<int64_t,2>> pre[n+5];
vector<array<int64_t,2>> fish[n+5];
for(int64_t i=0;i<m;i++){
if(ar[i][0]>1) consider[ar[i][0]-1].push_back(ar[i][1]);
if(ar[i][0]+1<=n) consider[ar[i][0]+1].push_back(ar[i][1]);
}
for(int64_t i=0;i<=n;i++){
consider[i].push_back(0);
sort(all(consider[i]));
consider[i].erase(unique(all(consider[i])),consider[i].end());
}
int64_t res[n+5];
memset(res,0,sizeof(res));
for(int64_t i=0;i<m;i++) fish[ar[i][0]].push_back({ar[i][1],ar[i][2]});
for(int64_t i=1;i<=n;i++){
fish[i].push_back({0,0});
sort(all(fish[i]));
int64_t cur=0;
for(auto x:fish[i]){
cur+=x[1];
pre[i].push_back({x[0],cur});
}
}
vector<int64_t> dp[n+5][2];
for(int64_t i=0;i<=n;i++){
dp[i][0].assign(sz(consider[i]),0);
dp[i][1].assign(sz(consider[i]),0);
}
auto get_sum=[&](int64_t i,int64_t j)->int64_t{
if(i<1 || i>n) return 0;
array<int64_t,2> bs={j+1,-1};
int64_t it=lower_bound(all(pre[i]),bs)-pre[i].begin();
if(it>0) return pre[i][it-1][1];
return 0;
};
for(int64_t i=1;i<=n;i++){
//start
for(int64_t j=0;j<sz(consider[i]);j++){
dp[i][0][j]=max(dp[i][0][j],(i>=3 ? res[i-3] : 0)+get_sum(i-1,consider[i][j]));
dp[i][1][j]=max(dp[i][1][j],(i>=3 ? res[i-3] : 0)
+get_sum(i-1,consider[i][j])+get_sum(i+1,consider[i][j]));
}
// calc increasing dp
vector<array<int64_t,2>> v;
int64_t cur=0;
for(int64_t j=0;j<sz(dp[i-1][0]);j++){
cur=max(cur,dp[i-1][0][j]-get_sum(i-1,consider[i-1][j]));
v.push_back({consider[i-1][j],cur});
}
auto get_val=[&](int64_t u,int64_t t)->int64_t{
array<int64_t,2> bs={u+1,-1};
int64_t it=lower_bound(all(v),bs)-v.begin();
if(it-t>=0 && it-t<sz(v)) return v[it-t][1];
return 0;
};
for(int64_t j=0;j<sz(consider[i]);j++){
int64_t u=consider[i][j];
int64_t val=get_sum(i-1,u)+get_val(u,1);
dp[i][0][j]=max(dp[i][0][j],val);
}
// calc decrasing dp
v.clear();
cur=0;
for(int64_t j=sz(dp[i-1][1])-1;j>=0;j--){
cur=max(cur,dp[i-1][1][j]);
v.push_back({consider[i-1][j],cur});
}
reverse(all(v));
for(int64_t j=0;j<sz(dp[i][1]);j++){
int64_t u=consider[i][j];
dp[i][1][j]=max(dp[i][1][j],get_val(u,0)-get_sum(i,u)+get_sum(i+1,u));
}
if(i>=2){ // new block
vector<array<int64_t,2>> arka[2];
cur=0;
for(int64_t j=0;j<sz(consider[i-2]);j++){
int64_t u=consider[i-2][j];
cur=max(cur,dp[i-2][0][j]);
cur=max(cur,dp[i-2][1][j]-get_sum(i-1,u));
arka[0].push_back({u,cur});
}
cur=0;
for(int64_t j=sz(consider[i-2])-1;j>=0;j--){
int64_t u=consider[i-2][j];
cur=max(cur,dp[i-2][0][j]+get_sum(i-1,u));
cur=max(cur,dp[i-2][1][j]);
arka[1].push_back({u,cur});
}
reverse(all(arka[1]));
auto get_kucuk=[&](int64_t u)->int64_t{
array<int64_t,2> bs={u+1,-1};
int64_t it=lower_bound(all(arka[0]),bs)-arka[0].begin();
if(it>0) return arka[0][it-1][1];
return 0;
};
auto get_buyuk=[&](int64_t u)->int64_t{
array<int64_t,2> bs={u+1,-1};
int64_t it=lower_bound(all(arka[1]),bs)-arka[1].begin();
if(it<sz(arka[1])) return arka[1][it][1];
return 0;
};
for(int64_t j=0;j<sz(consider[i]);j++){
int64_t u=consider[i][j];
dp[i][0][j]=max(dp[i][0][j],get_buyuk(u));
dp[i][0][j]=max(dp[i][0][j],get_kucuk(u)+get_sum(i-1,u));
}
for(int64_t j=0;j<sz(consider[i]);j++){
int64_t u=consider[i][j];
dp[i][1][j]=max(dp[i][1][j],get_buyuk(u)+get_sum(i+1,u));
dp[i][1][j]=max(dp[i][1][j],get_kucuk(u)+get_sum(i+1,u)+get_sum(i-1,u));
}
}
// inc to dec
v.clear();
cur=0;
for(int64_t j=sz(consider[i-1])-1;j>=0;j--){
int64_t u=consider[i-1][j];
cur=max(cur,dp[i-1][0][j]+get_sum(i,u));
v.push_back({u,cur});
}
reverse(all(v));
for(int64_t j=0;j<sz(consider[i]);j++){
int64_t u=consider[i][j];
dp[i][1][j]=max(dp[i][1][j],get_val(u,0)-get_sum(i,u)+get_sum(i+1,u));
}
for(int64_t j=0;j<sz(consider[i]);j++){
ans=max(ans,dp[i][0][j]+get_sum(i+1,consider[i][j]));
ans=max(ans,dp[i][1][j]);
}
res[i]=ans;
}
return max(res[n],ans);
}
