#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
const int MAX = 3010;
long long dp[MAX][MAX][3];
long long pref[MAX][MAX], mat[MAX][MAX];
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
// Build weight matrix
for (int i = 0; i < M; i++) {
mat[X[i]+1][Y[i]+1] += W[i];
}
// Build prefix sums for each column
for (int i = 1; i <= N; i++) {
for (int j = 1; j <= N; j++) {
pref[i][j] = pref[i][j-1] + mat[i][j];
}
}
// Initialize
for (int j = 1; j <= N; j++) {
dp[1][j][1] = pref[1][j];
dp[1][j][2] = dp[1][j][1];
}
// Transition
for (int i = 2; i <= N; i++) {
long long bestPrev = 0;
for (int k = 0; k <= N; k++)
bestPrev = max({bestPrev, dp[i-1][k][0], dp[i-1][k][1], dp[i-1][k][2]});
for (int j = 1; j <= N; j++) {
// state 0: block
dp[i][j][0] = bestPrev;
// state 1: take bottom j
dp[i][j][1] = max(dp[i][j-1][1], bestPrev + pref[i][j]);
// state 2: merge with previous column
dp[i][j][2] = max(dp[i][j-1][2], dp[i-1][j][1] + pref[i][j]);
}
}
long long ans = 0;
for (int j = 0; j <= N; j++)
ans = max({ans, dp[N][j][0], dp[N][j][1], dp[N][j][2]});
return ans;
}
