#include<bits/stdc++.h>
#include <vector>
#define fori(i,a,b) for(int i=a;i<=b;i++)
#define pb push_back
using namespace std;
typedef pair<int,long long> ii;
typedef tuple<int,int,int> tp;
const int M = 1e6 + 10;
const int N = 6e5 + 10;
const int mod = 1e9 + 7;
int n, m;
vector<ii> Q[N];
long long f[2][2][N];
long long tmp[2][N], mx[2][2][N];
long long max_weights(int N, int M,std::vector<int> X ,std::vector<int> Y ,std::vector<int> W )
{
n = N;
m = M;
for(int i = 1;i <= n; i++) Q[i].pb({0,0});
for(int i = 0;i < m; i++) {
X[i]++;
Y[i]++;
Q[X[i]].pb({Y[i],W[i]});
}
for(int i = 1;i <= n; i++) sort(Q[i].begin(), Q[i].end());
for(int i = 1;i <= n; i++) {
int pre = -1;
int sz = Q[i].size();
for(int j = 0;j <= sz - 1; j++) {
auto[pos, val] = Q[i][j];
if(pre != -1 && pre != pos - 1) {
Q[i].pb({pos - 1,0});
}
pre = pos;
}
if(pre != n) Q[i].pb({n,0});
sort(Q[i].begin(),Q[i].end());
}
for(int i = 2;i <= n; i++) {
vector<ii> pre, cur;
swap(pre,Q[i - 1]);
swap(cur,Q[i]);
//
long long sum = 0;
int v = 0;
for(int u = 0;u <= cur.size() - 1; u++) {
while(v != pre.size() && pre[v].first < cur[u].first) {
tmp[0][v] = f[0][i - 1 & 1][v] + sum;
tmp[1][v] = f[1][i - 1 & 1][v] + sum;
v++;
}
sum += cur[u].second;
}
while(v != pre.size()) {
tmp[0][v] = f[0][i - 1 & 1][v] + sum;
tmp[1][v] = f[1][i - 1 & 1][v] + sum;
v++;
}
for(int v = pre.size() - 1; v >= 0; v--) {
for(int e = 0;e <= 1; e++) {
mx[e][i & 1][v] = max(mx[e][i & 1][v + 1], tmp[e][v]);
}
}
v = 0;
sum = 0;
for(int u = 0;u <= cur.size() - 1; u++) {
while(v != pre.size() && pre[v].first < cur[u].first) v++;
sum -= cur[u].second;
f[1][i & 1][u] = max(mx[0][i & 1][v], mx[1][i & 1][v]) + sum;
//cout << cur[u].second << " ";
//cout << i << " " << 1 << " " << cur[u].first << " " << f[1][i & 1][u] << "\n";
}
//
sum = 0;
for(int v = pre.size() - 1;v >= 0; v--) {
tmp[0][v] = f[0][i - 1 & 1][v] + sum;
tmp[1][v] = f[1][i - 1 & 1][v];
sum += pre[v].second;
}
mx[0][i & 1][0] = tmp[0][0];
mx[1][i & 1][0] = tmp[1][0];
for(int v = 1;v <= pre.size() - 1; v++) {
for(int e = 0;e <= 1; e++) mx[e][i & 1][v] = max(mx[e][i & 1][v - 1], tmp[e][v]);
}
sum = 0;
int u = cur.size() - 1;
for(int v = pre.size() - 1;v >= 0; v--) {
while(u != -1 && pre[v].first <= cur[u].first) {
f[0][i & 1][u] = max({mx[0][i & 1][v] + sum,mx[1][i & 1][v]});
//cout << i << " " << cur[u].first << " " << f[0][i & 1][u] << "\n";
u--;
}
sum -= pre[v].second;
//cout << pre[v].first << " ";
}
while(u != -1) {
f[0][i & 1][u] = max({mx[0][i & 1][0] + sum,mx[1][i & 1][0]});
//cout << pre[v].first << " " << i << " " << 0 << " " << cur[u].first << " " << f[0][i & 1][u] << "\n";
u--;
}
for(int j = 0;j <= pre.size(); j++) {
f[0][i - 1 & 1][j] = f[1][i - 1 & 1][j] = tmp[0][j] = tmp[1][j] = 0;
}
swap(pre,Q[i - 1]);
swap(cur,Q[i]);
}
long long kq = 0;
for(int i = 0;i <= n; i++) kq = max({kq, f[0][n][i], f[1][n][i]});
return kq;
}
