#pragma GCC optimize("O3")
#include "fish.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
namespace{
const int mxn=1e5+5;
const ll inf=(ll)1e18;
vector<vector<ll>> dpl,dpr;
}
long long max_weights(int n, int m, std::vector<int> X, std::vector<int> Y,std::vector<int> W) {
auto st=clock();
vector<int> x=X;
vector<int> y=Y;
vector<int> w=W;
for(int i=0;i<m;i++){
x[i]++;
y[i]++;
//cout<<x[i]<<' '<<y[i]<<' '<<w[i]<<'\n';
}
vector<vector<int>> pos(n+1);
for(int i=0;i<m;i++){
pos[x[i]].push_back(i);
}
vector<vector<int>> ys(n+1);
vector<vector<ll>> pre(n+1);
vector<vector<int>> prv(n+1);
vector<vector<int>> nxt(n+1);
vector<int> sz(n+1);
for(int i=0;i<=n;i++){
ys[i].push_back(0);
for(auto v:pos[i]){
//ys[i].push_back(y[v]-1);
ys[i].push_back(y[v]);
}
if(i>0){
for(auto v:pos[i-1]){
ys[i].push_back(y[v]);
//ys[i].push_back(y[v]-1);
}
}
if(i<n){
for(auto v:pos[i+1]){
ys[i].push_back(y[v]);
//ys[i].push_back(y[v]-1);
}
}
sort(all(ys[i]));
ys[i].resize(unique(all(ys[i]))-ys[i].begin());
sz[i]=(int)ys[i].size();
pre[i]=vector<ll>(sz[i]);
for(auto v:pos[i]){
int j=lower_bound(all(ys[i]),y[v])-ys[i].begin();
pre[i][j]+=w[v];
}
for(int j=1;j<sz[i];j++){
pre[i][j]+=pre[i][j-1];
}
}
for(int i=0;i<=n;i++){
if(i>0){
prv[i]=vector<int>(sz[i]);
for(int j=0;j<sz[i];j++){
prv[i][j]=upper_bound(all(ys[i-1]),ys[i][j])-ys[i-1].begin()-1;
}
}
if(i<n){
nxt[i]=vector<int>(sz[i]);
for(int j=0;j<sz[i];j++){
nxt[i][j]=upper_bound(all(ys[i+1]),ys[i][j])-ys[i+1].begin()-1;
}
}
}
dpl.resize(n+1);
dpr.resize(n+1);
for(int i=0;i<=n;i++){
dpl[i]=vector<ll>(sz[i],-inf);
dpr[i]=vector<ll>(sz[i],-inf);
}
dpr[0][0]=0;
ll ans=0;
for(int i=0;i<n;i++){
{
int r=sz[i]-1;
ll mx=-inf;
for(int l=sz[i+1]-1;l>=0;l--){
while(r>=0 and ys[i][r]>=ys[i+1][l]){
mx=max(mx,dpr[i][r]);
r--;
}
dpl[i+1][l]=max(dpl[i+1][l],mx);
dpr[i+1][l]=max(dpr[i+1][l],mx);
}
}
{
int r=0;
ll mx=-inf;
for(int l=0;l<sz[i+1];l++){
while(r<sz[i] and ys[i][r]<=ys[i+1][l]){
mx=max(mx,dpr[i][r]-pre[i][r]);
r++;
}
dpl[i+1][l]=max(dpl[i+1][l],mx+pre[i][prv[i+1][l]]);
dpr[i+1][l]=max(dpr[i+1][l],mx+pre[i][prv[i+1][l]]);
}
}
//continue;
{
int l=sz[i]-1;
ll mx=-inf;
for(int r=sz[i+1]-1;r>=0;r--){
while(l>=0 and ys[i][l]>=ys[i+1][r]){
dpr[i+1][nxt[i][l]]=max(dpr[i+1][nxt[i][l]],dpl[i][l]+pre[i+1][nxt[i][l]]);
mx=max(mx,dpl[i][l]+pre[i+1][nxt[i][l]]);
l--;
}
dpl[i+1][r]=max(dpl[i+1][r],mx-pre[i+1][r]);
}
}
//continue;
{
int l=0;
ll mx=-inf;
for(int r=0;r<sz[i+1];r++){
while(l<sz[i] and ys[i][l]<=ys[i+1][r]){
//cout<<i<<' '<<l<<' '<<dpl[i][l]<<'\n';
mx=max(mx,dpl[i][l]);
l++;
}
dpr[i+1][r]=max(dpr[i+1][r],mx);
dpl[i+1][r]=max(dpl[i+1][r],mx);
}
}
}
for(int i=0;i<=n;i++){
for(int j=0;j<sz[i];j++){
//cout<<i<<' '<<j<<' '<<dpl[i][j]<<' '<<dpr[i][j]<<'\n';
ans=max({ans,dpl[i][j],dpr[i][j]});
}
}
return ans;
}
