#include "fish.h"
#include <bits/stdc++.h>
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
map<ll,ll> dp1[Nm];
map<ll,ll> dp2[Nm];
map<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-1);
scur.insert(p0.first);
scur.insert(p0.first+1);
}
}
if (i<(N-1)) {
for (pii p0: vctf[i+1]) {
scur.insert(p0.first-1);
scur.insert(p0.first);
scur.insert(p0.first+1);
}
}
for (pii p0: vctf[i]) {
scur.insert(p0.first-1);
scur.insert(p0.first);
scur.insert(p0.first+1);
}
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
for (ll yv: yc[i]) {
for (pii p0: dp1[i]) {
//dp2[i+1][yv]=max(dp2[i+1][yv],p0.second+getps(i,p0.first)-getps(i,max(p0.first,yv)));
dp2[i+1][yv]=max(dp2[i+1][yv],p0.second);
if (i>0) {
dp2[i+1][yv]=max(dp2[i+1][yv],p0.second+getps(i-1,p0.first)-getps(i-1,max(p0.first,yv)));
}
//[0,p0.first] -> [0,max(p0.first,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
for (ll yv: yc[i]) {
for (pii p0: dp2[i]) {
if (yv>=p0.first) {
dp2[i+1][yv]=max(dp2[i+1][yv],p0.second+getps(i-1,p0.first)-getps(i-1,yv));
}
}
}
//dp2 -> dp3
for (ll yv: yc[i]) {
for (pii p0: dp2[i]) {
if (yv<=p0.first) {
//FIX??
dp3[i+1][yv]=max(dp3[i+1][yv],p0.second+getps(i,yv)-getps(i,p0.first));
}
}
}
//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
for (ll yv: yc[i]) {
for (pii p0: dp3[i]) {
if (yv<=p0.first) {
dp3[i+1][yv]=max(dp3[i+1][yv],p0.second+getps(i,yv)-getps(i,p0.first));
if (dp3[i+1][yv]==14) {
//cout << "f2\n";
}
}
}
}
// 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;
}
