#include "fish.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define pll pair<ll,ll>
#define fs first
#define sc second
#define tiii tuple<int,int,int>
#define tlll tuple<ll,ll,ll>
const ll inf = 1e18;
const int mxn = 1e5+10;
vector<pii> fish[mxn];
vector<pll> dp[mxn][2];
ll big = 0;
ll f(int idx,int s,int e){
ll re = 0;
for(auto &[pos,w]:fish[idx]){
if(pos>s&&pos<=e)re += w;
}
return re;
}
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
std::vector<int> W) {
for(int i = 0;i<M;i++){
fish[X[i]].push_back(pii(Y[i],W[i]));
}
for(int i = 0;i<N;i++)fish[i].push_back(pii(N,0));
for(int i = 0;i<N;i++)sort(fish[i].begin(),fish[i].end());
{
vector<pii> v;
for(auto &[pos,w]:fish[0]){
if(pos)v.push_back(pii(pos-1,-1));
}
for(auto &[pos,w]:fish[1]){
v.push_back(pii(pos,w));
v.push_back(pii(pos,-1));
}
sort(v.begin(),v.end());
ll sum = 0;
for(auto &[a,b]:v){
if(b == -1)dp[0][0].push_back(pll(a,sum));
else sum += b;
}
sort(dp[0][0].begin(),dp[0][0].end());
dp[0][0].resize(unique(dp[0][0].begin(),dp[0][0].end())-dp[0][0].begin());
}
for(int i = 1;i<N;i++){
ll ls = 0,ms = 0,rs = 0;
vector<tlll> v;
//cerr<<"CALC "<<i<<":"<<endl;
for(auto &[pos,w]:fish[i]){
if(pos)v.push_back(tlll(pos-1,0,-1));
v.push_back(tlll(pos,-4,w));
}
for(auto &[pos,w]:fish[i-1]){
v.push_back(tlll(pos,0,-1));
v.push_back(tlll(pos,-3,w));
}
for(auto &[pos,w]:fish[i+1]){
v.push_back(tlll(pos,0,-1));
v.push_back(tlll(pos,-5,w));
}
sort(v.begin(),v.end());v.resize(unique(v.begin(),v.end())-v.begin());
for(auto &[pos,w]:dp[i-1][0])v.push_back(tlll(pos,-2,w));//tp == -2:trans
if(i-2>=0){
for(int j = 0;j<2;j++)for(auto &[pos,w]:dp[i-2][j])v.push_back(tlll(pos,-1,w));
}
sort(v.begin(),v.end());
ll mx1 = -inf,mx2 = -inf;
for(auto &[pos,tp,val]:v){
//cerr<<"["<<pos<<','<<tp<<','<<val<<','<<ls<<' '<<ms<<' '<<rs<<"]"<<endl;
if(tp == -5)rs+=val;
else if(tp == -4)ms+=val;
else if(tp == -3)ls+=val;
else if(tp == -2)mx1 = max(mx1,val-ms-ls);
else if(tp == -1)mx2 = max(mx2,val-ls);
else{
val = max({big+ls+rs,mx1+ls+rs,mx2+ls+rs});
}
}
//cerr<<endl;
mx1 = 0;
reverse(v.begin(),v.end());
for(auto &[pos,tp,val]:v){
if(tp == -5)rs -= val;
else if(tp == -1){
mx1 = max(mx1,val);
}
else if(tp == 0){
val = max(val,rs+mx1);
dp[i][0].push_back(pll(pos,val));
}
}
ls = rs = ms;
mx1 = mx2 = -inf;
v.clear();
for(auto &[pos,w]:fish[i]){
if(pos)v.push_back(tlll(pos-1,0,-1));
ms += w;
v.push_back(tlll(pos,-4,w));
}
for(auto &[pos,w]:fish[i-1]){
ls += w;
v.push_back(tlll(pos,0,-1));
v.push_back(tlll(pos,-3,w));
}
for(auto &[pos,w]:fish[i+1]){
rs += w;
v.push_back(tlll(pos,0,-1));
v.push_back(tlll(pos,-5,w));
}
sort(v.begin(),v.end());v.resize(unique(v.begin(),v.end())-v.begin());
for(auto &[pos,w]:dp[i-1][0])v.push_back(tlll(pos,2,w));//tp == 2:trans
for(auto &[pos,w]:dp[i-1][1])v.push_back(tlll(pos,2,w));//tp == 2:trans
sort(v.rbegin(),v.rend());
mx1 = -inf,mx2 = -inf;
for(auto &[pos,tp,val]:v){
if(tp == -5)rs-=val;
else if(tp == -4)ms-=val;
else if(tp == -3)ls-=val;
else if(tp == 2)mx1 = max(mx1,val);
else{
val = mx1-ms+rs;
dp[i][1].push_back(pll(pos,val));
}
}
if(i-2>=0){
for(int j = 0;j<2;j++)for(auto &[a,b]:dp[i-2][j])big = max(big,b);
}
}
ll ans = 0;
for(int i = 0;i<N;i++){
for(int j = 0;j<2;j++){
for(auto [a,b]:dp[i][j])ans = max(ans,b);
//cerr<<i<<' '<<j<<":";for(auto [a,b]:dp[i][j])cerr<<a<<','<<b<<' ';cerr<<endl;
}
}
return ans;
}
