#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
#define ll long long
ll max_weights(int n, int m, vector<int> x, vector<int> y, vector<int> w){
int maxH = 10; // Y[i] <= 8, pier heights 0..9 suffice
vector<vector<ll>> g(n, vector<ll>(maxH, 0));
for(int i = 0; i < m; i++)
g[x[i]][y[i]] = w[i];
// prefix[col][h] = sum of g[col][0..h-1]
vector<vector<ll>> prefix(n, vector<ll>(maxH + 1, 0));
for(int c = 0; c < n; c++)
for(int r = 0; r < maxH; r++)
prefix[c][r+1] = prefix[c][r] + g[c][r];
auto rangeSum = [&](int c, int lo, int hi) -> ll {
if(lo >= hi) return 0;
return prefix[c][hi] - prefix[c][lo];
};
int H = maxH + 1;
// dp[hpp][hp] = best total for fish at columns 0..col-2 fully resolved,
// with pier[col-2]=hpp, pier[col-1]=hp
vector<vector<ll>> dp(H, vector<ll>(H, -1));
vector<vector<ll>> ndp(H, vector<ll>(H, -1));
// Base: no columns processed yet, pier[-1]=0
for(int h = 0; h < H; h++)
dp[0][h] = 0;
for(int col = 1; col < n; col++){
for(int i = 0; i < H; i++)
fill(ndp[i].begin(), ndp[i].end(), -1);
for(int hpp = 0; hpp < H; hpp++){ // pier[col-2]
for(int hp = 0; hp < H; hp++){ // pier[col-1]
if(dp[hpp][hp] < 0) continue;
for(int h = 0; h < H; h++){ // pier[col]
// Resolve fish at col-1: not covered (row >= hp),
// caught by either neighbor (row < max(hpp, h))
ll val = dp[hpp][hp] + rangeSum(col-1, hp, max(hpp, h));
if(val > ndp[hp][h])
ndp[hp][h] = val;
}
}
}
swap(dp, ndp);
}
// Resolve fish at last column (n-1). Right neighbor doesn't exist (=0).
ll ans = 0;
for(int hpp = 0; hpp < H; hpp++){
for(int hp = 0; hp < H; hp++){
if(dp[hpp][hp] < 0) continue;
ll val = dp[hpp][hp] + rangeSum(n-1, hp, hpp);
ans = max(ans, val);
}
}
return ans;
}
