#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
bool deb = true;
int n, m;
vector<int> x, y;
vector<ll> w;
void dbg(vector<int> xx) {
if (!deb) return;
cout << "DBG: ";
for (auto x: xx) cout << x << " ";
cout << "\n";
}
ll max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
n = N;
m = M;
x = X;
y = Y;
for (auto x: W) w.push_back(x);
vector<vector<ll>> ps(n, vector<ll>(n, 0));
for (int i = 0; i < m; i++) {
ps[y[i]][x[i]] += w[i];
}
for (int c = 0; c < n; c++) {
for (int r = 1; r < n; r++) {
ps[r][c] += ps[r-1][c];
}
}
vector<vector<vector<ll>>> dp(n+1, vector<vector<ll>>(n+1, vector<ll>(n, 0)));
ll ans = 0;
for (int col = 1; col < n; col++) {
for (int cov = 0; cov <= n; cov++) {
for (int prev = 0; prev <= n; prev++) {
for (int prev2 = 0; prev2 <= n; prev2++) {
//dbg({col, cov, prev, prev2});
if (col == 1 && prev2 != 0) continue;
if (cov < prev) {
ll bon = ps[prev-1][col];
if (cov > 0) bon -= ps[cov-1][col];
dp[cov][prev][col] = max(dp[cov][prev][col], dp[prev][prev2][col-1] + bon);
}
else if (cov == prev) {
dp[cov][prev][col] = max(dp[cov][prev][col], dp[prev][prev2][col-1]);
}
else if (cov <= prev2) {
dp[cov][prev][col] = max(dp[cov][prev][col], dp[prev][prev2][col-1]);
}
else {
//dbg({-1});
int lo = max(prev2, prev);
int hi = max(cov-1, prev2-1);
ll bon = 0;
bon = ps[hi][col-1];
if (lo > 0) bon -= ps[lo-1][col-1];
bon = max(bon, 0LL);
dp[cov][prev][col] = max(dp[cov][prev][col], dp[prev][prev2][col-1] + bon);
}
ans = max(ans, dp[cov][prev][col]);
}
}
}
}
return ans;
}
