#include "fish.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
const int MAXN = 1e5+5;
struct dp {
int pos;
ll val, inc, dec;
};
vector <dp> F[MAXN];
bool cmp(dp x,dp y) {
if (x.pos != y.pos) return x.pos < y.pos;
return x.val < y.val;
}
ll max_weights(int N,int M,vector<int> X,vector<int> Y,vector<int> W) {
for (int i=0;i<M;i++) {
F[X[i]].push_back({Y[i],W[i],0,0});
}
for (int i=0;i<N;i++) {
F[i].push_back({0,0});
F[i].push_back({N,0});
sort(F[i].begin(),F[i].end(),cmp);
for (int j=1;j<(int)F[i].size();j++) {
F[i][j].val += F[i][j-1].val;
}
for (int j=F[i].size()-1;j>0;j--) {
F[i][j].val = F[i][j-1].val;
}
}
for (int i=1;i<N;i++) {
for (int j=0,k=0;j<(int)F[i].size();j++) {
while (k < (int)F[i-1].size() && F[i-1][k].pos <= F[i][j].pos) {
F[i][j].inc = max(F[i][j].inc,
F[i-1][k].inc - F[i-1][k].val);
k++;
}
if (j+1<(int)F[i].size()) {
F[i][j+1].inc = F[i][j].inc;
}
}
for (int j=0,jj=0;j<(int)F[i].size();j++) {
while (F[i-1][jj].pos < F[i][j].pos) jj++;
F[i][j].inc += F[i-1][jj].val;
}
for (int j=F[i].size()-1,k=F[i-1].size()-1,kk=F[i].size()-1;j>=0;j--) {
while (k >= 0 && F[i-1][k].pos >= F[i][j].pos) {
while (kk && F[i][kk-1].pos >= F[i-1][k].pos) kk--;
F[i][j].dec = max(F[i][j].dec,
max(F[i-1][k].dec,F[i-1][k].inc) + F[i][kk].val);
k--;
}
if (j) {
F[i][j-1].dec = F[i][j].dec;
}
}
for (int j=0;j<(int)F[i].size();j++) {
F[i][j].dec -= F[i][j].val;
}
if (i < 2) continue;
ll opt = 0;
for (int j=F[i].size()-1,k=F[i-2].size()-1,kk=F[i-1].size()-1;j>=0;j--) {
while (k >= 0 && F[i-2][k].pos >= F[i][j].pos) {
while (kk && F[i-1][kk-1].pos >= F[i-2][k].pos) kk--;
opt = max(opt, max(F[i-2][k].inc,F[i-2][k].dec) + F[i-1][kk].val);
k--;
}
F[i][j].inc = max(F[i][j].inc,opt);
}
opt = 0;
for (int j=0,jj=0,k=0;j<(int)F[i].size();j++) {
while (F[i-1][jj].pos < F[i][j].pos) jj++;
while (k < (int)F[i-2].size() && F[i-2][k].pos <= F[i][j].pos) {
opt = max(opt,max(F[i-2][k].inc,F[i-2][k].dec));
k++;
}
F[i][j].inc = max(F[i][j].inc, opt + F[i-1][jj].val);
}
}
ll ans = 0;
for (dp x : F[N-1]) {
ans = max(ans,max(x.inc,x.dec));
}
return ans;
}
