// Hallelujah, praise the one who set me free
// Hallelujah, death has lost its grip on me
// You have broken every chain, There's salvation in your name
// Jesus Christ, my living hope
#include <bits/stdc++.h>
#include "fish.h"
using namespace std;
#define REP(i, s, e) for (int i = (s); i < (e); i++)
#define RREP(i, s, e) for (int i = (s); i >= (e); i--)
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
typedef long long ll;
typedef long double ld;
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define SZ(_a) (int) _a.size()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
typedef vector<iii> viii;
#ifndef DEBUG
#define cerr if (0) cerr
#endif
const int INF = 1000000005;
const ll LINF = 1000000000000000005ll;
const int MAXN = 100005;
const int MAXM = 300005;
int n, m;
vii fish[MAXN];
vector<pair<int, ll>> dp[2][MAXN];
ll max_weights(int N, int M, vi X, vi Y, vi W) {
n = N; m = M;
REP (i, 0, m) {
X[i]++; Y[i]++;
fish[X[i]].pb({Y[i], W[i]});
}
REP (i, 1, n + 1) {
sort(ALL(fish[i]));
}
dp[0][0].pb({0, 0});
dp[1][0].pb({0, 0});
REP (i, 1, n + 1) {
vi cand;
for (auto [y, w] : fish[i - 1]) {
cand.pb(y);
}
for (auto [y, w] : fish[i]) {
cand.pb(y - 1);
}
for (auto [y, w] : fish[i + 1]) {
cand.pb(y);
}
cand.pb(0);
sort(ALL(cand));
cand.resize(unique(ALL(cand)) - cand.begin());
REP (z, 0, 2) {
REP (j, 0, SZ(cand)) {
dp[z][i].pb({cand[j], 0});
}
}
{ // .^
auto fptr = fish[i - 1].begin();
auto fdptr = fish[i - 1].begin();
auto dptr = dp[0][i - 1].begin();
ll sm = 0;
ll sub = 0;
ll mx = 0;
REP (j, 0, SZ(cand)) {
while (fptr != fish[i - 1].end() && fptr -> FI <= cand[j]) {
sm += fptr -> SE;
++fptr;
}
while (dptr != dp[0][i - 1].end() && dptr -> FI <= cand[j]) {
while (fdptr != fish[i - 1].end() && fdptr -> FI <= dptr -> FI) {
sub += fdptr -> SE;
++fdptr;
}
mxto(mx, dptr -> SE - sub);
++dptr;
}
mxto(dp[0][i][j].SE, mx + sm);
mxto(dp[1][i][j].SE, mx + sm);
}
}
{ // ^.
ll sm = 0;
auto fdptr = fish[i].begin();
auto fptr = fish[i].begin();
auto dptr = dp[1][i - 1].end();
while (fdptr != fish[i].end() && fdptr -> FI <= prev(dptr) -> FI) {
sm += fdptr -> SE;
++fdptr;
}
ll sub = 0;
while (fptr != fish[i].end() && fptr -> FI <= cand.back()) {
sub += fptr -> SE;
fptr++;
}
ll mx = 0;
RREP (j, SZ(cand) - 1, 0) {
while (fptr != fish[i].begin() && prev(fptr) -> FI > cand[j]) {
--fptr;
sub -= fptr -> SE;
}
while (dptr != dp[1][i - 1].begin() && prev(dptr) -> FI >= cand[j]) {
--dptr;
while (fdptr != fish[i].begin() && prev(fdptr) -> FI > dptr -> FI) {
--fdptr;
sm -= fdptr -> SE;
}
mxto(mx, dptr -> SE + sm);
}
mxto(dp[1][i][j].SE, mx - sub);
}
}
{ // ._^
auto fptr = fish[i - 1].begin();
auto dptr = dp[1][i - 2].begin();
ll sm = 0;
ll mx = 0;
REP (j, 0, SZ(cand)) {
while (fptr != fish[i - 1].end() && fptr -> FI <= cand[j]) {
sm += fptr -> SE;
++fptr;
}
while (dptr != dp[1][i - 2].end() && dptr -> FI <= cand[j]) {
mxto(mx, dptr -> SE);
++dptr;
}
mxto(dp[0][i][j].SE, mx + sm);
mxto(dp[1][i][j].SE, mx + sm);
}
}
{ // ^_.
ll sm = 0;
auto fdptr = fish[i - 1].begin();
auto dptr = dp[1][i - 2].end();
while (fdptr != fish[i - 1].end() && fdptr -> FI <= prev(dptr) -> FI) {
sm += fdptr -> SE;
++fdptr;
}
ll mx = 0;
RREP (j, SZ(cand) - 1, 0) {
while (dptr != dp[1][i - 2].begin() && prev(dptr) -> FI >= cand[j]) {
--dptr;
while (fdptr != fish[i - 1].begin() && prev(fdptr) -> FI > dptr -> FI) {
--fdptr;
sm -= fdptr -> SE;
}
mxto(mx, dptr -> SE + sm);
}
mxto(dp[0][i][j].SE, mx);
mxto(dp[1][i][j].SE, mx);
}
}
cerr << i << ' ' << 0 << '\n';
for (auto [y, v] : dp[0][i]) {
cerr << ' ' << y << ' ' << v << '\n';
}
cerr << i << ' ' << 1 << '\n';
for (auto [y, v] : dp[1][i]) {
cerr << ' ' << y << ' ' << v << '\n';
}
}
ll ans = 0;
for (auto [y, v] : dp[1][n]) {
mxto(ans, v);
}
return ans;
}
