#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
map<int,ll>fishies[100010];
map<int,ll>dp[100010][2];
ll ones(int col,int len){
auto it=fishies[col].upper_bound(len);
if(it==fishies[col].begin())return 0;
return (--it)->second;
}
ll max_weights(int N,int M,vector<int> X,vector<int> Y,vector<int> W) {
for(int i=0;i<M;i++)
fishies[X[i]+1][Y[i]+1]=W[i];
for(int i=1;i<=N;i++){
fishies[i][N+1];
fishies[i][1];
auto it=++fishies[i].begin();
while(it!=fishies[i].end())
it->second+=prev(it)->second,it++;
}
fishies[N+1][0];
dp[0][0][0];
dp[1][0][0];
for(int i=2;i<=N;i++){
for(auto[rw,j]:fishies[i]) {
ll K=0;
for(auto[rw2,vl]:dp[i-2][0])
K=max(K,vl+ones(i+1,rw-1)+max(0ll,ones(i-1,rw-1)-ones(i-1,rw2)));
for(auto[rw2,vl]:dp[i-2][1])
K=max(K,vl+ones(i+1,rw-1)+max(0ll,ones(i-1,rw-1)-ones(i-1,rw2)));
dp[i][1][rw-1]=K;
}
for(auto[rw,vl]:dp[i-1][0]) {
for(auto[rw2,j]:fishies[i]){
if(rw2-1>j) break;
ll K=ones(i+1,rw2-1)-ones(i,rw2-1)+vl;
dp[i][0][rw2-1]=max(dp[i][0][rw2-1],K);
}
}
for(auto[rw,vl]:dp[i-1][1]){
for(auto[rw2,j]:fishies[i]){
ll K=ones(i+1,rw2-1)-ones(i,min(rw,rw2-1))+
ones(i-1,rw2-1)-ones(i-1,min(rw2-1,rw))+vl;
dp[i][rw2>rw][rw2-1]=max(dp[i][rw2>rw][rw2-1],K);
}
}
}
ll ans=0;
for(auto[i,j]:dp[N][0])
ans=max(ans,j);
for(auto[i,j]:dp[N][1])
ans=max(ans,j);
return ans;
}
