#include <bits/stdc++.h>
#include "fish.h"
using namespace std;
typedef long long int lli;
typedef vector<lli> vi;
typedef pair<int,int> ii;
#define FOR(i,a,b) for(int i=(a);i<(b);++i)
#define ROF(i,a,b) for(int i=(b)-1;i>=(a);--i)
#define pb push_back
#define fi first
#define se second
#define all(v) begin(v),end(v)
const int INF = 2e9;
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
map<ii,lli> inc, dec;
inc[{-1,-INF}] = inc[{-1,INF}] = 0;
vector<pair<ii,lli>> ptw;
ptw.reserve(M+N);
FOR(i,0,M) ptw.pb({{X[i],Y[i]},W[i]});
FOR(i,0,N) ptw.pb({{i,INF},0});
sort(all(ptw));
vector<ii> pts;
FOR(i,0,M+N) {
pts.pb(ptw[i].fi);
}
//(not effective) const op
vector<vector<int>> cols(N);
vector<vi> wts(N);
FOR(i,0,M+N) {
int c = ptw[i].fi.fi,r=ptw[i].fi.se;
cols[c].pb(r);
if(wts[c].empty()) wts[c].pb(0);
wts[c].pb(wts[c].back()+ptw[i].se);
}
//counts fish in [{x,y1},{x,y2}], inclusive of endpoints
function<lli(lli,lli,lli)> countFish = [&] (lli x, lli y1, lli y2) {
if(x<0||x>=N||y1>y2) return 0LL;
else {
int l = lower_bound(all(cols[x]),y1) - begin(cols[x]);
int r = upper_bound(all(cols[x]),y2) - begin(cols[x]);
return wts[x][r]-wts[x][l];
}
};
map<ii,lli> colInc[3];
map<ii,lli> colDec;
//const op
int fishCount, fishIndex0, fishIndex;
FOR(i,0,N) {
int l = lower_bound(all(pts), ii{i,0}) - begin(pts);
int r = lower_bound(all(pts), ii{i+1,0}) - begin(pts);
int p = lower_bound(all(pts), ii{i-2,0}) - begin(pts);
FOR(j,l,r) {
if(j>l) colInc[0][pts[j]]=max(colInc[0][pts[j]],colInc[0][pts[j-1]]);
while(p<int(pts.size())&&pts[p].fi==i-2&&pts[p].se<=pts[j].se) {
colInc[0][pts[j]]=max(colInc[0][pts[j]],dec[pts[p]]);
p++;
}
}
fishCount = 0, fishIndex = lower_bound(all(pts), ii{i-1,0}) - begin(pts);
FOR(j,l,r) {
while(fishIndex < int(pts.size()) && pts[fishIndex].fi == i-1 && pts[fishIndex].se <= pts[j].se-1) fishCount += ptw[fishIndex++].se;
colInc[0][pts[j]] += fishCount;
}
p = lower_bound(all(pts), ii{i-2,0}) - begin(pts);
fishCount = 0, fishIndex = lower_bound(all(pts), ii{i-1,0}) - begin(pts);
while(p<int(pts.size())&&pts[p].fi==i-2) {
while(fishIndex < int(pts.size()) && pts[fishIndex].fi == i-1 && pts[fishIndex].se <= pts[p].se-1) fishCount += ptw[fishIndex++].se;
colInc[1][pts[l]] = max(colInc[1][pts[l]],dec[pts[p]]+fishCount);
p++;
}
FOR(j,l+1,r) colInc[1][pts[j]] = max(colInc[1][pts[j]],colInc[1][pts[j-1]]);
p = lower_bound(all(pts), ii{i-1,0}) - begin(pts);
FOR(j,l,r) {
if(j>l) colInc[2][pts[j]]=max(colInc[2][pts[j]],colInc[2][pts[j-1]]+countFish(i-1,pts[j-1].se,pts[j].se-1));
while(p<int(pts.size())&&pts[p].fi==i-1&&pts[p].se<=pts[j].se) {
colInc[2][pts[j]]=max(colInc[2][pts[j]],inc[pts[p]]+countFish(i-1,pts[p].se,pts[j].se-1));
p++;
}
}
p = lower_bound(all(pts), ii{i-1,INF}) - begin(pts);
ROF(j,l,r) {
if(i>0&&j<r-1) colDec[pts[j]]=max(colDec[pts[j]],colDec[pts[j+1]]+ptw[j].se);
while(p>=0&&pts[p].fi==i-1&&pts[p].se>=pts[j].se) {
colDec[pts[j]]=max(colDec[pts[j]],dec[pts[p]]+countFish(i,pts[j].se,pts[p].se-1));
p--;
}
}
FOR(j,l,r) {
FOR(k,0,3) {
inc[pts[j]] = max(inc[pts[j]],colInc[k][pts[j]]);
}
dec[pts[j]] = max(dec[pts[j]],colDec[pts[j]]);
}
dec[ii{i,INF}] = max(inc[ii{i,INF}],dec[ii{i,INF}]);
while(!inc.empty() && inc.begin()->fi.fi < i-1) inc.erase(inc.begin());
while(!dec.empty() && dec.begin()->fi.fi < i-1) dec.erase(dec.begin());
FOR(j,0,3) colInc[j].clear();
colDec.clear();
}
lli ans = max(inc[{N-1,INF}],dec.lower_bound({N-1,0})->second);
return ans;
}
