#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
struct pi{
int x,y; ll w;
};
struct pi2{
int y; ll up,down;
};
struct seg{
ll tree[1<<18];
int sz=1<<17;
void up(ll v,int tg){
tg|=sz;
for(tree[tg]=max(tree[tg],v);tg>>=1;)
tree[tg]=max(tree[tg<<1],tree[tg<<1|1]);
}
void init(ll v,int tg){
for(tree[tg|=sz]=v;tg>>=1;)
tree[tg]=max(tree[tg<<1],tree[tg<<1|1]);
}
ll qu(int l,int r){
ll re=0;
for(l|=sz,r|=sz;l<=r;l=(l+1)>>1,r=(r-1)>>1){
if(l&1) re=max(re,tree[l++]);
if(~r&1) re=max(re,tree[r--]);
}
return re;
}
};
seg t1,t2;
vector<pii> v;
vector<pi> megi;
ll dp[100010],inf=1e18;;
map<int,ll> mp[1000010];
bool comp(pi &a,pi &b){
if(a.x==b.x) return a.y<b.y;
return a.x<b.x;
}
ll max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
std::vector<int> W) {
for(int i=0;i<N;i++) v.push_back({i,0});
for(int i=0;i<M;i++){
if(X[i]>0) v.push_back({X[i]-1,Y[i]+1});
if(X[i]<N-1) v.push_back({X[i]+1,Y[i]+1});
}
for(int i=0;i<M;i++) megi.push_back({X[i],Y[i],W[i]});
sort(v.begin(),v.end()); v.erase(unique(v.begin(),v.end()),v.end());
sort(megi.begin(),megi.end(),comp);
int l1=0,l2=0,m=0;
for(int i=0;i<(1<<18);i++) t1.tree[i]=t2.tree[i]=-inf;
for(int i=0;i<N;i++){
ll cnt=0;
mp[i][-1]=0;
while(m<M&&megi[m].x==i){
cnt+=megi[m].w;
mp[i][megi[m].y]=cnt;
//printf("%d %d %lld\n",i,megi[m].y,cnt);
m++;
}
}
while(l2<(int)v.size()&&v[l2].first==0){
auto it = mp[1].upper_bound(v[l2].second-1); it--;
t2.up(it->second,v[l2].second);
l2++;
}
for(int i=1;i<N;i++){
vector<pi2> tmp;
while(l2<(int)v.size()&&v[l2].first==i){
auto it = mp[i-1].upper_bound(v[l2].second-1); it--;
ll up=t1.qu(0, v[l2].second)+it->second;
if(i==1) up=max(up,it->second);
else up=max(up,dp[i-2]+it->second);
it = mp[i].upper_bound(v[l2].second-1); it--;
ll down=t2.qu(v[l2].second, N)-it->second;
tmp.push_back({v[l2].second,up,down});
dp[i]=max(dp[i],max(up,down));
//printf("%d %d %lld %lld %lld\n",i,v[l2].second,up,down,it->second);
l2++;
}
if(i==N-1) break;
while(l1<(int)v.size()&&v[l1].first==i-1){
t1.init(-inf, v[l1].second);
t2.init(-inf, v[l1].second);
l1++;
}
for(auto x:tmp){
auto it = mp[i].upper_bound(x.y-1); it--;
t1.up(x.up-it->second, x.y);
it = mp[i+1].upper_bound(x.y-1); it--;
t2.up(max(x.up,x.down)+it->second, x.y);
}
}
return dp[N-1];
}
