#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <functional>
using namespace __gnu_pbds;
using namespace std;
typedef tree<int, null_type, less<int>, rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
//Dijkstra->set
//set.find_by_order(x) x-position value
//set.order_of_key(x) number of strictly less elements don't need *set.??
#define N 100005
#define wr cout << "Continue debugging\n";
#define all(x) (x).begin(), (x).end()
#define ll long long int
#define pii pair <ll, int>
#define pb push_back
#define ff first
#define ss second
ll max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w){
int nn = *max_element(all(y))+1;
vector<vector<ll>> a(n, vector<ll> (nn+1, 0));
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 < nn; j++){
a[i][j] += a[i][j-1];
}
}
vector<vector<pii>> dp(n, vector<pii>(nn+1, {0, -1}));
// vector<vector<vector<ll>>> dp(n, vector<vector<ll>>(nn+1, vector<ll>(2, 0)));
vector<ll> cur(n, 0);
for (int i = 0; i < nn; i++){
dp[1][i].ff = a[0][i];
}
cur[1] = a[1][nn-1];
for (int i = 2; i < n; i++){
for (int j = 0; j < nn; j++){
for (int k = 0; k <= j; k++){
ll x = dp[i-1][k].ff+(j > dp[i-1][k].ss ? a[i-1][j]-a[i-1][max(k,dp[i-1][k].ss)] : 0);
if (x > dp[i][j].ff) dp[i][j] = {x, k};
}
for (int k = j+1; k < nn; k++){
ll x = dp[i-1][k].ff+a[i][k]-a[i][j];
if (x > dp[i][j].ff) dp[i][j] = {x, k};
}
for (int k = 0; k < nn; k++){
ll x = a[i-1][max(j,k)]+dp[i-2][k].ff;
if (x > dp[i][j].ff) dp[i][j] = {x, -1};
}
ll x = cur[i-2]+a[i-1][j];
if (x > dp[i][j].ff) dp[i][j] = {x, -1};
}
cur[i] = max(cur[i], cur[i-1]);
for (int k = 0; k < nn; k++){
cur[i] = max(cur[i], dp[i-1][k].ff+a[i][k]);
}
}
return max(cur[n-1], (*max_element(all(dp[n-1]))).ff);
}
// int 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);
// }
