#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define forn(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(x) x.begin(), x.end()
using ll = long long;
#define pi pair<ll,ll>
#define f first
#define s second
const int N=100005;
vector<ll> pr[N];
vector<pi> f[N];
ll sum(int i, int j) {
int l=0, r=f[i].size();
while (l<r) {
int m=(l+r+1)>>1;
if (f[i][m-1].f>j) r=m-1;
else l=m;
}
return pr[i][r];
}
vector<pi> dp[N], dp2[N], dp3[N];
vector<ll> prmx[N], prmx2[N], sfmx[N];
ll prmxquery(int i, int j) {
return prmx[i].back();
}
ll prmx2query(int i, int j) {
int l=0, r=dp3[i].size();
while (l<r) {
int m=(l+r+1)>>1;
if (dp3[i][m-1].f >= j) r=m-1;
else l=m;
}
return prmx2[i][r];
}
ll sfmxquery(int i, int j) {
return sfmx[i][0];
}
ll max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) {
forn(i,m) {
f[x[i]+1].pb({y[i]+1,w[i]});
}
for(int i=1;i<=n;++i) {
sort(all(f[i]));
f[i].pb({n+1,0});
pr[i]={0};
forn(j,f[i].size()) pr[i].pb(pr[i].back()+f[i][j].s);
}
dp[0].pb({0,0});
dp[0].pb({n,0});
pr[0]={0,0,0};
dp2[0]=dp3[0]=dp[0];
prmx[0]={0,0};
prmx2[0]=sfmx[0]=prmx[0];
pr[n+1]={0,0,0};
for(int i=1; i<=n; ++i) {
if (f[i][0].f!=1) {
int j=0;
ll d=0;
if (i>=2) {
d=max(d,prmxquery(i-2,j)+sum(i-1,j));
d=max(d,sfmxquery(i-2,j));
}
d=max(d,prmx2query(i-1,j)+sum(i-1,j));
d=max(d,prmxquery(i-1,j));
ll d3=d;
d=max(d,sfmxquery(i-1,j)-sum(i,j));
ll d2=d+sum(i+1,j);
dp[i].pb({j,d});
dp2[i].pb({j,d2});
dp3[i].pb({j,d3});
}
for(auto&x:f[i]) {
int j=x.f-1;
ll d=0;
if (i>=2) {
d=max(d,prmxquery(i-2,j)+sum(i-1,j));
d=max(d,sfmxquery(i-2,j));
}
d=max(d,prmx2query(i-1,j)+sum(i-1,j));
d=max(d,prmxquery(i-1,j));
ll d3=d;
d=max(d,sfmxquery(i-1,j)-sum(i,j));
ll d2=d+sum(i+1,j);
dp[i].pb({j,d});
dp2[i].pb({j,d2});
dp3[i].pb({j,d3});
}
prmx[i]={0};
prmx2[i]=sfmx[i]=prmx[i];
for (int j=0; j<dp[i].size(); ++j) {
prmx[i].pb(max(prmx[i].back(),dp[i][j].s));
prmx2[i].pb(max(prmx2[i].back(),dp3[i][j].s-sum(i,dp3[i][j].f)));
}
reverse(all(dp2[i]));
for (int j=0; j<dp2[i].size(); ++j) {
sfmx[i].pb(max(sfmx[i].back(),dp2[i][j].s));
}
reverse(all(dp2[i]));
reverse(all(sfmx[i]));
}
ll ans=0;
for(auto&x:dp[n]) ans=max(ans,x.s);
return ans;
return prmx[n].back();
}
