#include "fish.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
using ll = long long; using pii = pair<ll,ll>;
const ll Nm = 1e5+5; const ll INF = 1e18;
vector<pii> vctf[Nm];
map<ll,ll> psw[Nm]; //current x, lower bound at y0 -> sum of ws with y>=y0
vector<ll> yc[Nm]; //ys to consider
gp_hash_table<ll,ll> dp1[Nm];
gp_hash_table<ll,ll> dp2[Nm];
gp_hash_table<ll,ll> dp3[Nm];
//dp1: ...,a,0; store a
//dp2: ...,a,b; a<=b; store b
//dp3: ...,a,b; a>=b; store b
ll getps(ll xc, ll v) {
auto A0 = *(psw[xc].lower_bound(v));
return A0.second;
}
ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
for (ll i=0;i<M;i++) {
vctf[X[i]].push_back({Y[i],W[i]});
}
for (ll i=0;i<Nm;i++) {
sort(vctf[i].begin(),vctf[i].end());
psw[i][INF]=0;
ll swcur = 0;
for (ll T=(vctf[i].size()-1);T>=0;T--) {
swcur += vctf[i][T].second;
psw[i][vctf[i][T].first]=swcur;
}
}
for (ll i=0;i<N;i++) {
set<ll> scur;
if (i>0) {
for (pii p0: vctf[i-1]) {
scur.insert(p0.first);
}
}
if (i<(N-1)) {
for (pii p0: vctf[i+1]) {
scur.insert(p0.first);
}
}
yc[i].push_back(0);
for (ll x0: scur) {
if (x0>=0) {
yc[i].push_back(x0+1);
}
}
}
//DP: # of terms active -> value at <=(current x) SO FAR
//dp1: ...,a,0; store a
//dp2: ...,a,b; a<=b; store b
//dp3: ...,a,b; a>=b; store b; MUST go down
dp1[0][0]=0;
for (ll i=0;i<N;i++) {
//dp1 -> dp1
for (pii p0: dp1[i]) {
dp1[i+1][0]=max(dp1[i+1][0],p0.second);
}
//dp1 -> dp2
ll PMAX1 = -INF;
for (pii p0: dp1[i]) {
PMAX1 = max(PMAX1,p0.second);
}
for (ll yv: yc[i]) {
dp2[i+1][yv]=max(dp2[i+1][yv],PMAX1);
}
if (i>0) {
vector<pii> dp1v;
for (pii p0: dp1[i]) {
dp1v.push_back(p0);
}
sort(dp1v.begin(),dp1v.end());
vector<pii> vt1;
vt1.push_back({-INF,-INF});
ll cmax = -INF;
for (pii p0: dp1v) {
ll vcur = p0.second+getps(i-1,p0.first);
if (vcur > cmax) {
cmax = vcur;
vt1.push_back({p0.first,vcur});
}
}
for (ll yv: yc[i]) {
auto A0 = *(--lower_bound(vt1.begin(),vt1.end(),(pii){(ll)yc,(ll)INF}));
dp2[i+1][yv]=max(dp2[i+1][yv],(A0).second-getps(i-1,yv));
}
}
//dp2 -> dp1
for (pii p0: dp2[i]) {
dp1[i+1][p0.first]=max(dp1[i+1][p0.first],p0.second+getps(i,0)-getps(i,p0.first));
}
//dp2 -> dp2
vector<pii> vt1;
vector<pii> dp2v;
for (pii p0: dp2[i]) {
dp2v.push_back(p0);
}
sort(dp2v.begin(),dp2v.end());
vt1.push_back({-INF,-INF});
ll cmax = -INF;
for (pii p0: dp2v) {
ll vcur = p0.second+getps(i-1,p0.first);
if (vcur > cmax) {
cmax = vcur;
vt1.push_back({p0.first,vcur});
}
}
for (ll yv: yc[i]) {
auto A0 = *(--lower_bound(vt1.begin(),vt1.end(),(pii){(ll)yc,(ll)INF}));
dp2[i+1][yv]=max(dp2[i+1][yv],(A0).second-getps(i-1,yv));
}
//dp2 -> dp3
vector<pii> vt4I,vt4;
for (pii p0: dp2[i]) {
vt4I.push_back({p0.first,p0.second-getps(i,p0.first)});
}
sort(vt4I.rbegin(),vt4I.rend());
ll cmaxv0 = -INF;
for (pii p0: vt4I) {
if (p0.second>cmaxv0) {
cmaxv0 = p0.second;
vt4.push_back(p0);
}
}
vt4.push_back({INF,-INF});
sort(vt4.begin(),vt4.end());
for (ll yv: yc[i]) {
pii p0 = *lower_bound(vt4.begin(),vt4.end(),(pii){yv,-INF});
dp3[i+1][yv]=max(dp3[i+1][yv],p0.second+getps(i,yv));
}
//dp3 -> dp1
for (pii p0: dp3[i]) {
dp1[i+1][p0.first]=max(dp1[i+1][p0.first],p0.second+getps(i,0)-getps(i,p0.first));
}
//dp3 -> dp3
vector<pii> vt5I,vt5;
for (pii p0: dp3[i]) {
vt5I.push_back({p0.first,p0.second-getps(i,p0.first)});
}
sort(vt5I.rbegin(),vt5I.rend());
ll cmaxv = -INF;
for (pii p0: vt5I) {
if (p0.second>cmaxv) {
cmaxv = p0.second;
vt5.push_back(p0);
}
}
vt5.push_back({INF,-INF});
sort(vt5.begin(),vt5.end());
for (ll yv: yc[i]) {
pii p0 = *lower_bound(vt5.begin(),vt5.end(),(pii){yv,-INF});
dp3[i+1][yv]=max(dp3[i+1][yv],p0.second+getps(i,yv));
}
// cout << "print states after reading column i="<<i<<"\n";
// cout << "dp1:\n";
// for (pii p0: dp1[i+1]) {
// cout << p0.first << ": " <<p0.second<<"\n";
// }
// cout << "dp2:\n";
// for (pii p0: dp2[i+1]) {
// cout << p0.first << ": " <<p0.second<<"\n";
// }
// cout << "dp3:\n";
// for (pii p0: dp3[i+1]) {
// cout << p0.first << ": " <<p0.second<<"\n";
// }
}
ll ans = 0;
for (pii p0: dp1[N]) {
ans = max(ans,p0.second);
}
for (pii p0: dp2[N]) {
ans = max(ans,p0.second);
}
for (pii p0: dp3[N]) {
ans = max(ans,p0.second);
}
return ans;
}
