// #include <algorithm>
#include <vector>
#include <iostream>
// #include <queue>
using namespace std;
#define ll long long
vector<vector<ll>> dp;
vector<vector<ll>> g;
ll n;
ll calcDp(ll ind, ll p){
ll mx = 0;
dp[ind][p] = 0;
if(ind >= 3){
for(ll i = 0; i<9; i++){
dp[ind][p] = max(calcDp(ind-3, i), dp[ind][p]);
}
for(ll i = 0; i<p; i++) dp[ind][p] += g[ind-1][i] + ((ind<n-1)?g[ind+1][i]:0);
}
if(ind >= 2){
ll sum = 0;
for(ll i = 0; i<p; i++) sum += g[ind-1][i] + ((ind<n-1)?g[ind+1][i]:0);
for(ll i = 0; i<9; i++){
if(i<=p && i>0) sum -= g[ind-1][i-1];
mx = max(mx, sum + dp[ind-2][i]);
}
dp[ind][p] = max(dp[ind][p], mx);
sum = 0;
for(ll i = 0; i<p; i++) sum += ((ind<n-1)?g[ind+1][i]:0);
for(ll i = 0; i<9; i++){
if(i<=p && i>0) sum -= g[ind][i-1];
dp[ind][p] = max(dp[ind][p], sum + dp[ind-1][i]);
}
}
if(ind <= 1){
for(ll i = 0; i<p; i++){
dp[ind][p] += (i<n-1?g[ind+1][i]:0) + (0<ind?g[ind-1][i]:0);
}
}
return dp[ind][p];
}
ll max_weights(int n1, int m, vector<int> x, vector<int> y, vector<int> w){
n = n1;
dp.assign(n, vector<ll>(9, -1));
g.assign(n, vector<ll>(9, 0));
for(ll i = 0; i<m; i++){
g[x[i]][y[i]] = w[i];
}
ll mx = 0;
for(ll i = 0; i<n; i++){
for(ll j = 0; j<9; j++){
if(dp[i][j] == -1) calcDp(i, j);
mx = max(mx, dp[i][j]);
}
}
return mx;
}
