// #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, int p){
if(dp[ind][p] != -1) return dp[ind][p];
if(ind == 0){
return dp[ind][p] = 0;
}
for(int i = 0; i<10; i++){
ll tmp = calcDp(ind-1, i);
for(auto j = i; j< p; j++){
tmp += g[ind-1][j];
}
dp[ind][p] = max(dp[ind][p], tmp);
}
if(ind == 1) return dp[ind][p];
for(int i = 0; i<10; i++){
for(int j = 0; j<10; j++){
ll tmp = calcDp(ind-2, i);
for(int c = j; c<max(i, p); c++){
tmp += g[ind-1][c];
}
dp[ind][p] = max(dp[ind][p], tmp);
}
}
return dp[ind][p];
}
ll max_weights(int n1, int m, vector<int> x1, vector<int> y1, vector<int>w1){
n = n1;
g.assign(n, vector<ll>(10, 0));
dp.assign(n+1, vector<ll>(10, -1));
for(int i = 0; i<m; i++){
g[x1[i]][y1[i]] = w1[i];
}
return calcDp(n, 0);
}
