#include "fish.h"
#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
const int inf = 1e18;
using namespace std;
long long max_weights(signed N, signed M, std::vector<signed> X, std::vector<signed> Y,
std::vector<signed> W)
{
int n = N,m = M;
vector<array<int,3>> v(m);
for(int i = 0; i < m; i++)
v[i] = {X[i],Y[i],W[i]};
for(int i = 0; i < n; i++)
v.push_back({i,-1,0}),v.push_back({i,n,0});
m = v.size();
sort(v.begin(),v.end());
vector<pii> dp(m,{0,0});
int ans = 0;
vector<vector<int>> grt(n);
for(int i = 0; i < m; i++)
grt[v[i][0]].push_back(i);
for(auto&a:grt)
sort(a.begin(),a.end(),[&](int a,int b){return v[a][1]<v[b][1];});
int l = 0;
{
int pref = 0;
for(int j :grt[0]){
pref+=v[j][2],dp[j].ss = pref;
}
}
for(int i = 1; i < n; i++)
{
{int mx = 0;
for(int j : grt[i-1])
mx = max({mx,dp[j].ff,dp[j].ss});
for(int j: grt[i])
dp[j] = {mx,mx};}
{
//levo
int lv = 0,pref = 0,ts =0, mx = 0;
reverse(grt[i].begin(),grt[i].end());
reverse(grt[i-1].begin(),grt[i-1].end());
for(int j : grt[i-1])
pref+=v[j][2];
for(int j : grt[i])
ts+=v[j][2];
for(int j : grt[i])
{
while(lv < grt[i-1].size() &&
v[grt[i-1][lv]][1] > v[j][1])
pref-=v[grt[i-1][lv]][2],mx = max(dp[grt[i-1][lv]].ff,mx),
lv++;
dp[j].ff = max(dp[j].ff,mx-pref+ts);
ts-=v[j][2];
}
}
{
//desno
int lv = 0,pref = 0,ts =0, mx = 0;
reverse(grt[i].begin(),grt[i].end());
reverse(grt[i-1].begin(),grt[i-1].end());
{
int big = 0;
for(int j : grt[i-1])
big = max(big,dp[j].ff);
for(int j :grt[i])
ts+=v[j][2],dp[j].ss =max(dp[j].ss,big+ts);
}
ts = 0;
for(int j : grt[i])
{
ts+=v[j][2];
while(lv < grt[i-1].size() &&
v[grt[i-1][lv]][1] < v[j][1])
mx = max(mx,dp[grt[i-1][lv]].ss-pref),lv++;
dp[j].ss = max(dp[j].ss,ts+mx);
pref+=v[j][2];
}
}
}
pii fin = *max_element(dp.begin(),dp.end());
return fin.ff;
}
