#include "fish.h"
#include <bits/stdc++.h>
#define pb push_back
#define eb emplace_back
#define md (tl + tr) / 2
#define TL v + v, tl, md
#define TR v + v + 1, md + 1, tr
#define all(x) (x).begin(), (x).end()
#define F first
#define S second
using namespace std;
typedef long long ll;
const int N = 3e5 + 7;
const ll INF = 1e18 + 7;
int n, m;
ll t[2][4 * N], c[2][4 * N], x[N], y[N], w[N], mx[N];
vector <pair <int, ll>> v[N];
ll get(int tp, int l, int r, int v = 1, int tl = 0, int tr = n) {
if (tl >= l and tr <= r)
return t[tp][v];
if (tl > r or l > tr)
return -INF;
return max(get(tp, l, r, TL), get(tp, l, r, TR));
}
ll getc(int tp, int l, int r, int v = 1, int tl = 0, int tr = n) {
if (tl > r or l > tr)
return 0;
if (tl >= l and tr <= r)
return c[tp][v];
return getc(tp, l, r, TL) + getc(tp, l, r, TR);
}
void upd(int tp, int p, ll x, int v = 1, int tl = 0, int tr = n) {
t[tp][v] = max(t[tp][v], x);
if (tl == tr)
return;
if (p <= md)
upd(tp, p, x, TL);
else
upd(tp, p, x, TR);
}
void updc(int tp, int p, ll x, int v = 1, int tl = 0, int tr = n) {
c[tp][v] += x;
if (tl == tr)
return;
if (p <= md)
updc(tp, p, x, TL);
else
updc(tp, p, x, TR);
}
void del(int v = 1, int tl = 0, int tr = n) {
if (t[0][v] == -INF and t[1][v] == -INF)
return;
t[0][v] = -INF;
t[1][v] = -INF;
if (tl != tr) {
del(TL);
del(TR);
}
}
void delc(int tp, int v = 1, int tl = 0, int tr = n) {
if (c[tp][v] == 0)
return;
c[tp][v] = 0;
if (tl != tr) {
delc(tp, TL);
delc(tp, TR);
}
}
ll max_weights(int N, int M, vector <int> X, vector <int> Y, vector <int> W) {
n = N, m = M;
for (int i = 1;i <= m;i++) {
x[i] = X[i - 1] + 1;
y[i] = Y[i - 1] + 1;
w[i] = W[i - 1];
v[x[i]].eb(y[i], w[i]);
}
vector <array <ll, 3>> vu;
for (int i = 1;i <= n;i++) {
sort(all(v[i]));
delc(i & 1);
for (auto now : v[i]) {
updc(i & 1, now.F, now.S);
}
v[i].eb(n + 1, 0);
del();
for (auto now : vu) {
if (now[0] == 0)
upd(0, now[1], now[2] - getc(!(i & 1), 0, now[1]));
else
upd(1, now[1], now[2] + getc(i & 1, 0, now[1]));
}
vu.clear();
mx[i] = mx[i - 1];
for (int j = 0;j < v[i].size();j++) {
int y = v[i][j].F - 1;
ll val = max(getc(!(i & 1), 0, y) + get(0, 0, y), mx[i - 1]);
mx[i] = max(mx[i], val);
vu.pb({0, y, val});
vu.pb({1, y, val});
}
for (int j = v[i].size() - 1;j >= 0;j--) {
int y = v[i][j].F - 1;
ll val = max(get(1, y, n) - getc(i & 1, 0, y), mx[i - 1]);
mx[i] = max(mx[i], val);
vu.pb({1, y, val});
}
for (int j = v[i - 1].size() - 1;j >= 0;j--) {
int y = v[i - 1][j].F - 1;
ll val = max(get(1, y, y), mx[i - 1]);
mx[i] = max(mx[i], val);
vu.pb({0, y, val});
}
// cout << mx[i] << ' ';
}
return mx[n];
}
// void solve() {
// int n, m;
// cin >> n >> m;
// vector <int> x(m), y(m), w(m);
// for (int i = 0;i < m;i++)
// cin >> x[i] >> y[i] >> w[i];
// cout << max_weights(n, m, x, y, w);
// }
// signed main() {
// solve();
// return 0;
// }
