#include "fish.h"
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define ll long long
#define ld long double
#define ull unsigned long long
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<long long, long long>
#define vi vector<int>
#define vl vector<long long>
#define pb push_back
#define rep(i, b) for(int i = 0; i < (b); ++i)
#define rep2(i,a,b) for(int i = a; i <= (b); ++i)
#define rep3(i,a,b,c) for(int i = a; i <= (b); i+=c)
#define count_bits(x) __builtin_popcountll((x))
#define all(x) (x).begin(),(x).end()
#define siz(x) (int)(x).size()
#define forall(it,x) for(auto& it:(x))
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,tree_order_statistics_node_update> ordered_set;
//mt19937 mt;void random_start(){mt.seed(chrono::time_point_cast<chrono::milliseconds>(chrono::high_resolution_clock::now()).time_since_epoch().count());}
//ll los(ll a, ll b) {return a + (mt() % (b-a+1));}
const int INF = 1e9+50;
const ll INF_L = 1e18+40;
const ll MOD = 1e9+7;
vector<pll> dps[100003][2];
vector<pll> vals[100003];
ll max_weights(int n, int m, vi X, vi Y, vi W)
{
rep(i,m) X[i] += 2;
rep(i,m)
{
vals[X[i]].pb({Y[i]+1,W[i]});
}
rep(i,n+2) sort(all(vals[i]));
dps[0][0] = {{0,0}};
dps[1][0] = {{0,0}};
dps[0][1] = {{0,0}};
dps[1][1] = {{0,0}};
rep2(i,2,n+1)
{
vi dps_sort;
forall(it,vals[i-1]) dps_sort.pb(it.ff);
forall(it,vals[i+1]) dps_sort.pb(it.ff);
sort(all(dps_sort));
vi d = {0};
vi right_add = {0};
dps[i][0].pb({0,0});
dps[i][1].pb({0,0});
int pop = -1;
forall(it,dps_sort)
{
if(it != pop)
{
d.pb(it);
right_add.pb(0);
dps[i][0].pb({it,0});
dps[i][1].pb({it,0});
}
pop = it;
}
// right add
int cur_right = 0;
ll right_sum = 0;
rep(j,siz(d))
{
while(cur_right < siz(vals[i+1]) && vals[i+1][cur_right].ff <= d[j])
{
right_sum += vals[i+1][cur_right].ss;
cur_right++;
}
right_add[j] = right_sum;
}
// smaller space
ll max_dp = 0;
forall(it,dps[i-2][0]) max_dp = max(max_dp,it.ss);
forall(it,dps[i-2][1]) max_dp = max(max_dp,it.ss);
rep(j,siz(d))
{
dps[i][0][j].ss = max_dp;
dps[i][1][j].ss = max_dp;
}
// bigger space
max_dp = 0;
ll left_sum = 0;
int cur_left_val = 0;
int cur_left_dp = 0;
rep(j,siz(d))
{
while(cur_left_dp < siz(dps[i-2][0]) && dps[i-2][0][cur_left_dp].ff <= d[j])
{
while(cur_left_val < siz(vals[i-1]) && vals[i-1][cur_left_val].ff <= dps[i-2][0][cur_left_dp].ff)
{
left_sum += vals[i-1][cur_left_val].ss;
cur_left_val++;
}
max_dp = max(max_dp,dps[i-2][0][cur_left_dp].ss-left_sum);
max_dp = max(max_dp,dps[i-2][1][cur_left_dp].ss-left_sum);
cur_left_dp++;
}
while(cur_left_val < siz(vals[i-1]) && vals[i-1][cur_left_val].ff <= d[j])
{
left_sum += vals[i-1][cur_left_val].ss;
cur_left_val++;
}
rep(d,2) dps[i][d][j].ss = max(dps[i][d][j].ss,max_dp + left_sum);
}
// smaller
max_dp = 0;
forall(it,dps[i-1][0]) max_dp = max(max_dp,it.ss);
ll my_sum = 0;
forall(it,vals[i]) my_sum += it.ss;
int cur_my_vals = siz(vals[i])-1;
for(int j = siz(d)-1; j >= 0; j--)
{
while(cur_my_vals >= 0 && vals[i][cur_my_vals].ff > d[j])
{
my_sum -= vals[i][cur_my_vals].ss;
cur_my_vals--;
}
dps[i][0][j].ss = max(dps[i][0][j].ss,max_dp-my_sum);
}
// bigger
max_dp = 0;
left_sum = 0;
my_sum = 0;
cur_my_vals = 0;
cur_left_val = 0;
cur_left_dp = 0;
rep(j,siz(d))
{
while(cur_left_dp < siz(dps[i-1][0]) && dps[i-1][0][cur_left_dp].ff <= d[j])
{
while(cur_my_vals < siz(vals[i]) && vals[i][cur_my_vals].ff <= dps[i-1][0][cur_left_dp].ff)
{
my_sum += vals[i][cur_my_vals].ss;
cur_my_vals++;
}
while(cur_left_val < siz(vals[i-1]) && vals[i-1][cur_left_val].ff <= dps[i-1][0][cur_left_dp].ff)
{
left_sum += vals[i-1][cur_left_val].ss;
cur_left_val++;
}
max_dp = max(max_dp,dps[i-1][1][cur_left_dp].ss-my_sum-left_sum);
cur_left_dp++;
}
while(cur_my_vals < siz(vals[i]) && vals[i][cur_my_vals].ff <= dps[i-1][0][cur_left_dp].ff)
{
my_sum += vals[i][cur_my_vals].ss;
cur_my_vals++;
}
while(cur_left_val < siz(vals[i-1]) && vals[i-1][cur_left_val].ff <= dps[i-1][0][cur_left_dp].ff)
{
left_sum += vals[i-1][cur_left_val].ss;
cur_left_val++;
}
dps[i][1][j].ss = max(dps[i][1][j].ss,max_dp+left_sum);
}
dps[i][0][0].ss = 0;
dps[i][1][0].ss = 0;
forall(it,dps[i-1][0]) dps[i][0][0].ss = max(dps[i][0][0].ss,it.ss);
forall(it,dps[i-1][1]) dps[i][0][0].ss = max(dps[i][0][0].ss,it.ss);
forall(it,dps[i-2][0]) dps[i][0][0].ss = max(dps[i][1][0].ss,it.ss);
forall(it,dps[i-2][1]) dps[i][0][0].ss = max(dps[i][1][0].ss,it.ss);
rep(j,siz(d))
{
rep(d,2) dps[i][d][j].ss += right_add[j];
}
}
ll ans = 0;
forall(it,dps[n+1][0]) ans = max(ans,it.ss);
forall(it,dps[n+1][1]) ans = max(ans,it.ss);
return ans;
}
