#include <algorithm>
#include <vector>
#include <iostream>
// #include <queue>
using namespace std;
#define ll long long
vector<vector<ll>> dp;
vector<vector<ll>> g;
vector<vector<ll>> newDp;
ll n;
ll find_max(ll col, ll p1, ll p2){
ll ans = 0;
for(ll p3 = 0; p3<((col == 1)? 1:10); p3++){
ll tmp = 0;
tmp += dp[p2][p3];
for(ll k = p2; k<max(p1, p3); k++) tmp += g[col-1][k];
ans = max(ans, tmp);
}
return ans;
}
ll max_weights(int n1, int m, vector<int> x1, vector<int> y1, vector<int>w1){
n = n1;
g.assign(n, vector<ll>(12, 0));
dp.assign(12, vector<ll>(12, -1));
newDp.assign(12, vector<ll>(12, 0));
for(ll i = 0; i<m; i++){
g[x1[i]][y1[i]] = w1[i];
}
ll mx = 0;
for(ll col = 1; col<n; col++){
dp = newDp;
newDp.assign(12, vector<ll>(12, -1));
for(ll i = 0; i<10; i++){
for(ll j = 0; j<10; j++){
newDp[i][j] = find_max(col, i, j);
mx = max(mx, newDp[i][j]);
}
}
}
return mx;
}
