#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
int n;
vector<vector<long long>> b;
vector<vector<long long>> nxt;
vector<vector<long long>> pre;
vector<vector<vector<long long>>> dp;
vector<vector<pair<int, int>>> in_col;
long long bt(int col, int prev, int cur) {
if (col == n) {
return 0;
}
long long& ret = dp[col][prev][cur];
if (ret != -1) {
return ret;
}
ret = 0;
if (col == 0) {
for (int i = 0; i < (int) in_col[col + 1].size(); ++i) {
long long w = max(0LL, pre[col + 1][i] - b[col][cur]);
ret = max(ret, bt(col + 1, cur, i) + w);
}
} else if (col == n - 1) {
ret = max(0LL, nxt[col - 1][prev] - b[col][cur]);
} else {
for (int i = 0; i < (int) in_col[col + 1].size(); ++i) {
long long w = max(0LL, max(pre[col + 1][i], nxt[col - 1][prev]) - b[col][cur]);
ret = max(ret, bt(col + 1, cur, i) + w);
}
}
return ret;
}
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
n = N;
in_col.resize(N);
for (int i = 0; i < M; ++i) {
in_col[X[i]].push_back({Y[i], W[i]});
}
for (int i = 0; i < N; ++i) {
sort(in_col[i].begin(), in_col[i].end());
in_col[i].push_back({N, 0});
}
dp.resize(N);
dp[0].resize(1);
dp[0][0].assign(in_col[0].size(), -1);
for (int i = 1; i < N; ++i) {
dp[i].resize(in_col[i - 1].size());
for (int j = 0; j < (int) in_col[i - 1].size(); ++j) {
dp[i][j].assign(in_col[i].size(), -1);
}
}
pre.resize(N);
for (int col = 1; col < N; ++col) {
pre[col].resize(in_col[col].size());
for (int i = 0; i < (int) in_col[col].size(); ++i) {
int ptr = 0;
long long sum = 0;
while (ptr < (int) in_col[col - 1].size() && in_col[col - 1][ptr].first < in_col[col][i].first) {
sum += in_col[col - 1][ptr].second;
ptr++;
}
pre[col][i] = sum;
}
}
nxt.resize(N);
for (int col = 0; col < N - 1; ++col) {
nxt[col].resize(in_col[col].size());
for (int i = 0; i < (int) in_col[col].size(); ++i) {
int ptr = 0;
long long sum = 0;
while (ptr < (int) in_col[col + 1].size() && in_col[col + 1][ptr].first < in_col[col][i].first) {
sum += in_col[col + 1][ptr].second;
ptr++;
}
nxt[col][i] = sum;
}
}
b.resize(N);
for (int col = 0; col < N; ++col) {
b[col].resize((int) in_col[col].size());
for (int i = 1; i < (int) in_col[col].size(); ++i) {
b[col][i] = b[col][i - 1] + in_col[col][i - 1].second;
}
}
long long ans = 0;
//ans = bt(0, 0, 0);
for (int i = 0; i < (int) in_col[0].size(); ++i) {
ans = max(ans, bt(0, 0, i));
}
return ans;
}
