#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct segTree{
ll tree[400002];
void init(int i, int l, int r){
tree[i] = -1e18;
if(l==r) return;
int m = (l+r)>>1;
init(i*2, l, m);
init(i*2+1, m+1, r);
}
void update(int i, int l, int r, int x, ll v){
if(l==r){
tree[i] = max(tree[i], v);
return;
}
int m = (l+r)>>1;
if(x<=m) update(i*2, l, m, x, v);
else update(i*2+1, m+1, r, x, v);
tree[i] = max(tree[i*2], tree[i*2+1]);
}
ll query(int i, int l, int r, int s, int e){
if(r<s || e<l) return -1e18;
if(s<=l && r<=e) return tree[i];
int m = (l+r)>>1;
return max(query(i*2, l, m, s, e), query(i*2+1, m+1, r, s, e));
}
} treeL, treeR;
struct Point{
int x, y;
ll w;
Point(){}
Point(int x, int y, ll w): x(x), y(y), w(w){}
bool operator<(const Point &r)const{
if(x != r.x) return x < r.x;
return y<r.y;
}
};
int n, k;
ll DP[300002][2];
ll sum[100005];
vector<Point> vec[100005];
vector<Point> checkL[100005], checkR[100005];
ll ans;
ll max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W){
n = N, k = M;
for(int i=0; i<k; i++){
vec[X[i]+1].push_back(Point(X[i]+1, Y[i]+1, W[i]));
sum[X[i]+1] += W[i];
}
for(int i=0; i<=n; i++){
sort(vec[i].begin(), vec[i].end());
DP[i][0] = DP[i][1] = -1e18;
}
treeL.init(1, 0, n+1);
treeR.init(1, 0, n+1);
treeL.update(1, 0, n+1, 0, 0);
for(int i=1; i<=n; i++){
/// Checklist
for(Point p: checkL[i]) treeL.update(1, 0, n+1, 0, p.w);
for(Point p: checkR[i]) treeR.update(1, 0, n+1, n+1, p.w);
/// DP[?][0] -> DP[i][1]
{
for(Point p: vec[i-1]){ /// max 계산
treeL.update(1, 0, n+1, p.y, treeL.query(1, 0, n+1, 0, p.y-1) + p.w);
}
ll v = treeL.query(1, 0, n+1, 0, n+1);
DP[i][1] = max(DP[i][1], v);
}
/// DP[?][1] -> DP[i][1] (with gap)
if(i >= 3){
ll v = DP[i-2][1] + sum[i-1];
DP[i][1] = max(DP[i][1], v);
}
/// DP[?][1] -> DP[i][1] (with no gap)
if(i >= 2){
ll v = DP[i-1][1];
DP[i][1] = max(DP[i][1], v);
}
/// DP[?][1] -> DP[i][0]
{
reverse(vec[i].begin(), vec[i].end());
for(Point p: vec[i]){
treeR.update(1, 0, n+1, p.y, treeR.query(1, 0, n+1, p.y+1, n+1) + p.w);
}
reverse(vec[i].begin(), vec[i].end());
ll v = treeR.query(1, 0, n+1, 0, n+1);
DP[i][0] = max(DP[i][0], v);
}
checkR[i+1].push_back(Point(i+1, n+1, DP[i][1]));
checkL[i+2].push_back(Point(i+2, 0, DP[i][0]));
ans = max({ans, DP[i][0], DP[i][1]});
// printf("%d: %lld %lld\n", i, DP[i][0], DP[i][1]);
}
return ans;
}
