#include "fish.h"
#include<bits/stdc++.h>
using namespace std;
#define F first
#define S second
#define pb push_back
#define vll vector<ll>
#define pll pair<ll, ll>
typedef long long ll;
namespace{
const ll mxN=3e6+5; // warning
const ll inf=1e18;
ll dp[mxN][2];
ll dp2[mxN];
ll mxdp2[mxN];
ll a[mxN];
vll pre[mxN];
vll v[mxN];
vll v2[mxN];
vll v3[mxN];
vector<pll> con;
ll id(pll tar){
return lower_bound(con.begin(), con.end(), tar)-con.begin();
}
bool check(pll tar){
ll tep=id(tar);
if(tep>=(ll) con.size()) return false;
if(con[tep].F!=tar.F || con[tep].S!=tar.S){
return false;
}
return true;
}
ll id2(ll tar, ll idx){
return lower_bound(v[idx].begin(), v[idx].end(), tar)-v[idx].begin();
}
ll id3(ll tar, ll idx){
return lower_bound(v2[idx].begin(), v2[idx].end(), tar)-v2[idx].begin();
}
ll id4(ll tar, ll idx){
return lower_bound(v3[idx].begin(), v3[idx].end(), tar)-v3[idx].begin();
}
ll pre1(ll idx, ll tar){
ll tep=upper_bound(v3[idx].begin(), v3[idx].end(), tar)-v3[idx].begin();
tep--;
if(tep<0) return 0LL;
return pre[idx][tep];
}
ll f_big(ll idx, ll tar){
ll tep=id2(tar, idx);
return v[idx][tep];
}
ll f_small(ll idx, ll tar){
ll tep=upper_bound(v2[idx].begin(), v2[idx].end(), tar)-v2[idx].begin();
tep--;
if(tep<0) return -1LL;
return v2[idx][tep];
}
ll ans;
}
long long max_weights(int n, int m, vector<int> X, vector<int> Y,
vector<int> W) {
memset(a, 0, sizeof(a));
memset(dp, 0, sizeof(dp));
memset(dp2, 0, sizeof(dp2));
memset(mxdp2, 0, sizeof(mxdp2));
for(ll i=0;i<m;i++){
con.pb({X[i], Y[i]});
con.pb({X[i], Y[i]-1});
con.pb({X[i], Y[i]+1});
v[X[i]].pb(Y[i]);
v2[X[i]].pb(Y[i]+1);
v3[X[i]].pb(Y[i]+1);
}
for(ll i=0;i<n;i++){
v[i].pb(n);
v2[i].pb(0);
v3[i].pb(0);
con.pb({i, n});
con.pb({i, 0});
sort(v[i].begin(), v[i].end());
v[i].erase(unique(v[i].begin(), v[i].end()), v[i].end());
sort(v2[i].begin(), v2[i].end());
v2[i].erase(unique(v2[i].begin(), v2[i].end()), v2[i].end());
sort(v3[i].begin(), v3[i].end());
v3[i].erase(unique(v3[i].begin(), v3[i].end()), v3[i].end());
}
sort(con.begin(), con.end());
con.erase(unique(con.begin(), con.end()), con.end());
for(ll i=0;i<m;i++){
a[id({X[i], Y[i]})]=W[i];
}
for(ll i=0;i<n;i++){
ll p=0;
for(auto &it:v3[i]){
ll cur=p;
if(check({i, it-1})){
cur+=a[id({i, it-1})];
}
pre[i].pb(cur);
p=cur;
}
}
ans=0;
for(auto &it:v[0]){
ll tep=f_small(1, it);
ll tep2=id({1, tep});
ll tep3=id({0, it});
ll tep4=pre1(1, tep);
dp2[tep2]=max(dp2[tep2], dp[tep3][0]+tep4);
dp2[tep2]=max(dp2[tep2], dp[tep3][1]+tep4);
}
for(ll i=1;i<n;i++){
for(ll k=0;k<2;k++){
if(k==0){
ll mx=-inf;
ll pt=0;
for(auto &it:v[i]){
while(pt<(ll) v[i-1].size() && v[i-1][pt]<=it){
mx=max(mx, dp[id({i-1, v[i-1][pt]})][0]-pre1(i-1, v[i-1][pt]));
pt++;
}
ll val=mx+pre1(i-1, it);
ll tep2=id({i, it});
dp[tep2][k]=max(dp[tep2][k], val);
}
mx=-inf;
pt=0;
// ll pt2=0;
for(auto &it:v[i]){
// mx=max(mx, dp2[i-1][j-1]-pre[i-1][j-1]);
while(pt<(ll) v2[i-1].size() && v2[i-1][pt]<=it-1){
mx=max(mx, dp2[id({i-1, v2[i-1][pt]})]-pre1(i-1, v2[i-1][pt]));
pt++;
}
ll val=mx+pre1(i-1, it);
ll tep2=id({i, it});
dp[tep2][k]=max(dp[tep2][k], val);
dp[tep2][k]=max(dp[tep2][k], mxdp2[i-1]);
}
}
else{
ll mx=-inf;
ll pt=(ll) v[i-1].size()-1;
for(ll j=(ll) v[i].size()-1;j>=0;j--){
ll it=v[i][j];
while(pt>=0 && v[i-1][pt]>=it){
ll tep2=id({i-1, v[i-1][pt]});
ll tep3=pre1(i, v[i-1][pt]);
mx=max(mx, dp[tep2][0]+tep3);
mx=max(mx, dp[tep2][1]+tep3);
pt--;
}
ll tep2=id({i, it});
dp[tep2][k]=max(dp[tep2][k], mx-pre1(i, it));
}
}
for(auto &it:v[i]){
ans=max(ans, dp[id({i, it})][k]);
}
if(i<n-1){
for(auto &it:v[i]){
ll tep=f_small(i+1, it);
ll tep2=id({i+1, tep});
ll tep3=id({i, it});
ll tep4=pre1(i+1, tep);
dp2[tep2]=max(dp2[tep2], dp[tep3][0]+tep4);
dp2[tep2]=max(dp2[tep2], dp[tep3][1]+tep4);
}
}
}
// for(ll t=0;t<=n;t++){
dp2[id({i, 0})]=max(dp2[id({i, 0})], mxdp2[i-1]);
// }
for(auto &it:v2[i]){
// dp2[id({i, it})]=max(dp2[id({i, it})], dp[id({i-1, f_big(i-1, it)})][0]+pre1(i, it));
// dp2[id({i, it})]=max(dp2[id({i, it})], dp[id({i-1, f_big(i-1, it)})][1]+pre1(i, it));
ll tep2=dp2[id({i, it})];
mxdp2[i]=max(mxdp2[i], tep2);
ans=max(ans, tep2);
}
}
return ans;
}
