#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) {
vector<vector<int>> a(n, vector<int>(n));
for (int i = 0; i < m; i++) {
a[x[i]][y[i]] = w[i];
}
for (int i = 0; i < n; i++) {
for (int j = 1; j < n; j++) {
a[i][j] += a[i][j - 1];
}
}
int K = 8;
if (n < K) {
K = n;
}
vector<vector<vector<vector<ll>>>> dp(n - 2, vector<vector<vector<ll>>>(K + 1, vector<vector<ll>>(K + 1, vector<ll>(K + 1))));
if (n == 2) {
return max(a[0][n - 1], a[1][n - 1]);
}
ll res = 0;
for (int i = 0; i <= K; i++) {
for (int j = 0; j <= K; j++) {
for (int q = 0; q <= K; q++) {
int val = 0;
if (n > 3) {
val = a[3][q];
}
int v2 = max(0, a[2][j] - a[2][q]);
int v1 = max(0, max(a[1][i], a[1][q]) - a[1][j]);
int v0 = max(0, a[0][j] - a[0][i]);
dp[0][i][j][q] = val + v0 + v1 + v2;
res = max(res, dp[0][i][j][q]);
}
}
}
for (int beg = 1; beg < n - 2; beg++) {
for (int i = 0; i <= K; i++) {
for (int j = 0; j <= K; j++) {
for (int q = 0; q <= K; q++) {
for (int k = 0; k <= K; k++) {
int val = 0;
if (beg < n - 3) {
val = a[beg + 3][q];
}
ll nv = dp[beg - 1][k][i][j];
nv += val;
nv -= a[beg + 2][min(j, q)];
nv += max(0, a[beg + 1][q] - a[beg + 1][max(i, j)]);
dp[beg][i][j][q] = max(dp[beg][i][j][q], nv);
}
res = max(res, dp[beg][i][j][q]);
}
}
}
}
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';
}*/
