#include <bits/stdc++.h>
#include "fish.h"
using namespace std;
#define fi first
#define se second
typedef long long ll;
typedef long double ld;
mt19937 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
ll inf = 1e18;
ll max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w) {
int K = min(n - 1, 8);
vector<vector<ll>> a(n, vector<ll>(K + 2));
for (int i = 0; i < m; i++) {
a[x[i]][y[i] + 1] = w[i];
}
for (int i = 0; i < n; i++) {
for (int j = 1; j < K + 2; j++) {
a[i][j] += a[i][j - 1];
}
}
vector<vector<ll>> dp(K + 2, vector<ll>(K + 2)), newdp(K + 2, vector<ll>(K + 2));
ll res = 0;
for (int i = 0; i <= K + 1; i++) {
for (int j = 0; j <= K + 1; j++) {
ll val = 0;
if (n > 2) {
val = a[2][j];
}
ll v1 = max(0ll, a[1][i] - a[1][j]);
ll v0 = max(0ll, a[0][j] - a[0][i]);
dp[i][j] = val + v0 + v1;
res = max(res, dp[i][j]);
}
}
newdp = dp;
for (int beg = 1; beg < n - 1; beg++) {
for (int i = 0; i <= K + 1; i++) {
for (int j = 0; j <= K + 1; j++) {
for (int k = 0; k <= K + 1; k++) {
ll val = 0;
if (beg < n - 2) {
val = a[beg + 2][j];
}
ll nv = dp[k][i];
nv += val;
nv -= a[beg + 1][min(j, i)];
nv += max(0ll, a[beg][j] - a[beg][max(i, k)]);
newdp[i][j] = max(newdp[i][j], nv);
}
res = max(res, newdp[i][j]);
}
}
dp = newdp;
}
return res;
}
/*
signed main() {
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) << '\n';
}*/
