#include "fish.h"
#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("inline")
#define pb push_back
#define eb emplace_back
#define md ((tl + tr) >> 1)
#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], dp[N];
vector <pair <int, ll>> v[N], dd[N];
int uc[2][N], u[N], T, Tc[2];
void checkc(int v, int tp) {
if (uc[tp][v] < Tc[tp]) {
c[tp][v] = 0;
}
uc[tp][v] = Tc[tp];
}
void check(int v) {
if (u[v] < T) {
t[0][v] = t[1][v] = -INF;
}
u[v] = T;
}
ll get(int tp, int l, int r, int v = 1, int tl = 0, int tr = n) {
check(v);
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) {
checkc(v, tp);
if (tl > r or l > tr or c[tp][v] == 0)
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) {
check(v);
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) {
checkc(v, tp);
c[tp][v] += x;
if (tl == tr)
return;
if (p <= md)
updc(tp, p, x, TL);
else
updc(tp, p, x, TR);
}
ll max_weights(int N, int M, vector <int> X, vector <int> Y, vector <int> W) {
n = N, m = M;
bool ok = 1;
ll s = 0;
for (int i = 1;i <= m;i++) {
x[i] = X[i - 1] + 1;
if (!(x[i] & 1))
ok = 0;
y[i] = Y[i - 1] + 1;
w[i] = W[i - 1];
s += w[i];
dd[y[i]].eb(x[i], w[i]);
}
for (int i = 1;i <= n;i++) {
for (auto now : dd[i]) {
v[now.F].eb(i, now.S);
}
}
if (ok)
return s;
vector <array <ll, 3>> vu;
v[0].eb(n + 1, 0);
for (int i = 1;i <= n;i++) {
T = i;
Tc[i & 1] = i;
ll s = 0;
for (auto now : v[i]) {
s += now.S;
updc(i & 1, now.F, now.S);
}
v[i].eb(n + 1, 0);
for (int j = v[i - 1].size() - 1;j >= 0;j--) {
int y = v[i - 1][j].F - 1;
dp[y] = -INF;
}
for (int j = 0;j < vu.size();j++) {
array <ll, 3> now = vu[j];
if (now[0] == 0)
upd(0, now[1], now[2] - getc(!(i & 1), 0, now[1]));
else {
ll z = now[2] + getc(i & 1, 0, now[1]);
dp[now[1]] = max(dp[now[1]], z);
}
}
vu.clear();
mx[i] = mx[i - 1];
int k = 0;
ll ss = 0;
for (int j = 0;j < v[i].size();j++) {
int y = v[i][j].F - 1;
while (v[i - 1][k].F <= y) {
ss += v[i - 1][k].S;
k++;
}
ll val = max(ss + get(0, 0, y), mx[i - 1]);
mx[i] = max(mx[i], val);
vu.pb({0, y, val});
vu.pb({1, y, val});
}
k = v[i - 1].size() - 1;
ss = -INF;
for (int j = v[i].size() - 1;j >= 0;j--) {
int y = v[i][j].F - 1;
s -= v[i][j].S;
while (k >= 0 and v[i - 1][k].F - 1 >= y) {
ss = max(ss, dp[v[i - 1][k].F - 1]);
k--;
}
ll val = max(ss - s, 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(dp[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;
// }
