#ifndef mikevui
// #include "task.h"
#endif // mikevui
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double dou;
#define pii pair<int, int>
#define fi first
#define se second
#define pb push_back
#define MASK(x) (1LL<<(x))
#define BITj(x, j) (((x)>>(j))&1)
template<typename T> bool maximize(T &x, const T &y) {
if (x < y) {x = y; return 1;}
return 0;
}
template<typename T> bool minimize(T &x, const T &y) {
if (x > y) {x = y; return 1;}
return 0;
}
const int maxn = 1e5+5;
const ll INF = (ll)3e18+7;
int n, m;
vector<pii> a[maxn];
vector<ll> dp1[maxn], dp0[maxn];
ll ans = 0;
ll max_weights(int N, int M, int X[], int Y[], int W[]) {
n = N;
m = M;
for (int i= 0 ;i < m ;i++) {
int x = X[i]+1, y = Y[i]+1, w = W[i];
a[x].pb({y, w});
}
for (int i = 1; i <= n; i++) {
sort(a[i].begin(), a[i].end());
}
ll ma10, ma11, ma0;
ma10 = ma11 = ma0 = 0;
//dp
for (int pos= 1; pos <= n; pos++) {
//init
dp1[pos].assign((int)a[pos].size(), -INF);
dp0[pos].assign((int)a[pos].size(), -INF);
int len = (int)a[pos].size();
//inc -> 0
if (pos < n) {
int j = -1;
ll malas = 0;
for (int i = 0; i < len; i++) {
dp0[pos][i] = max(ma10, ma0);
if (i > 0) maximize(dp0[pos][i], dp0[pos][i-1]);
if (pos > 1) {
while (j+1 < (int)a[pos-1].size() && a[pos-1][j+1].fi < a[pos][i].fi) {
++j;
maximize(malas, dp0[pos-1][j]);
}
if (j > -1 && a[pos-1][j].fi < a[pos][i].fi) {
maximize(dp0[pos][i], malas);
}
}
dp0[pos][i] += a[pos][i].se;
}
}
//dec -> 1
if (pos > 1) {
int j = (int)a[pos-1].size();
ll malas = 0;
for (int i = len-1; i >= 0; i--) {
dp1[pos][i] = max(ma11, ma0);
if (i < len-1) maximize(dp1[pos][i], dp1[pos][i+1]);
while (j-1 >= 0 && a[pos-1][j-1].fi > a[pos][i].fi) {
++j;
maximize(malas, dp1[pos-1][j]);
}
if (j < (int)a[pos-1].size() && a[pos-1][j].fi > a[pos][i].fi) {
maximize(dp1[pos][i], malas);
}
dp1[pos][i] += a[pos][i].se;
}
}
//update ma
for (int i = 0; i < len; i++) {
maximize(ma10, dp1[pos][i]);
maximize(ans, dp1[pos][i]);
maximize(ans, dp0[pos][i]);
}
if (pos > 1) {
for (int i = 0; i < (int)a[pos-1].size(); i++) {
maximize(ma11, dp1[pos-1][i]);
maximize(ma0, dp0[pos-1][i]);
}
}
}
// for (int pos = 1; pos <= n; pos++) {
// cout << "curpos " << pos << "\n";
// for (int i= 0; i < (int)a[pos].size(); i++) {
// cout << a[pos][i].fi << ' ' << a[pos][i].se << ' ' << (dp0[pos][i] <= -INF ? -1 : dp0[pos][i]) << ' ' << (dp1[pos][i] <= -INF ? -1 : dp1[pos][i]) << "\n";
// }
// }
return ans;
}
#ifdef mikevui
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
// #define name "task"
// if (fopen(name".inp", "r")) {
// freopen(name".inp", "r", stdin);
// freopen(name".out", "w", stdout);
// }
int N, M, X[maxn], Y[maxn], W[maxn];
cin >> N >> M;
for (int i = 0; i < M; i++) {
cin >> X[i] >> Y[i] >> W[i];
}
cout << max_weights(N, M, X, Y, W);
}
#endif // mikevui
/*
5 4
0 2 5
1 1 2
4 4 1
3 3 3
*/
Compilation message
/usr/bin/ld: /tmp/ccrX6aKx.o: in function `main':
grader.cpp:(.text.startup+0x25e): undefined reference to `max_weights(int, int, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >, std::vector<int, std::allocator<int> >)'
collect2: error: ld returned 1 exit status
