#include "fish.h"
#include "bits/stdc++.h"
using namespace std;
typedef long long ll;
#define all(x) x.begin(),x.end()
ll max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w){
vector<ll> sum[n],fish[n],pier[n];
vector<pair<ll,ll>> inf_fish[n];
for(int i=0;i<m;i++) inf_fish[x[i]].push_back({y[i]+1,w[i]});
for(int i=0;i<n;i++){
sum[i].push_back(0); fish[i].push_back(0); pier[i].push_back(0);
sort(all(inf_fish[i]));
for(int j=0;j<(int)inf_fish[i].size();j++){
fish[i].push_back(inf_fish[i][j].first);
sum[i].push_back(inf_fish[i][j].second);
if(i) pier[i-1].push_back(inf_fish[i][j].first);
if(i!=n-1) pier[i+1].push_back(inf_fish[i][j].first);
}
}
vector<ll> left[n],me[n],right[n];
for(int i=0;i<n;i++){
left[i].assign(pier[i].size(),0);
me[i].assign(pier[i].size(),0);
right[i].assign(pier[i].size(),0);
//sum:
for(int j=1;j<(int)sum[i].size();j++)
sum[i][j]+=sum[i][j-1];
//left:
if(i){
for(int j=0,k=0;j<(int)pier[i].size();){
if(k==(int)fish[i-1].size()-1){
left[i][j]=k;
j++;
}
else if(pier[i][j]>=fish[i-1][k] && pier[i][j]<fish[i-1][k+1]){
left[i][j]=k;
j++;
}
else k++;
}
}
//me:
for(int j=0,k=0;j<(int)pier[i].size();){
if(k==(int)fish[i].size()-1){
me[i][j]=k;
j++;
}
else if(pier[i][j]>=fish[i][k] && pier[i][j]<fish[i][k+1]){
me[i][j]=k;
j++;
}
else k++;
}
//right:
if(i!=n-1){
for(int j=0,k=0;j<(int)pier[i].size();){
if(k==(int)fish[i+1].size()-1){
right[i][j]=k;
j++;
}
else if(pier[i][j]>=fish[i+1][k] && pier[i][j]<fish[i+1][k+1]){
me[i][j]=k;
j++;
}
else k++;
}
}
}
vector<vector<vector<ll>>> dp[n];
for(int i=0;i<n;i++){
int j=(i>=2) ? pier[i-2].size() : 1;
int k=(i) ? pier[i-1].size() : 1;
int l=pier[i].size();
dp[i].assign(j,vector<vector<ll>>(k,vector<ll>(l,0)));
}
for(int i=1;i<n;i++){
int size_j=(i>=2) ? pier[i-2].size() : 1;
for(int j=0;j<size_j;j++){
for(int k=0;k<(int)pier[i-1].size();k++){
ll prev=0;
int size_l=(i>=3) ? pier[i-3].size() : 1;
for(int l=0;l<size_l;l++)
prev=max(prev,dp[i-1][l][j][k]);
for(int l=0;l<(int)pier[i].size();l++){
dp[i][j][k][l]+=prev;
if(pier[i-1][k]>=pier[i][l]){
dp[i][j][k][l]+=sum[i][right[i-1][k]]-sum[i][me[i][l]];
}
else{
if(i>=2 && pier[i-2][j]>=pier[i-1][k])
dp[i][j][k][l]+=sum[i-1][left[i][l]]-sum[i-1][right[i-2][j]];
else
dp[i][j][k][l]+=sum[i-1][left[i][l]]-sum[i-1][me[i-1][k]];
}
}
}
}
}
ll res=0;
int size_i=(n>=3) ? pier[n-3].size() : 1;
for(int i=0;i<size_i;i++)
for(int j=0;j<(int)pier[n-2].size();j++)
for(int k=0;k<(int)pier[n-1].size();k++)
res=max(res,dp[n-1][i][j][k]);
return res;
}
