#include "fish.h"
#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
using namespace std;
#define mxn 5000
long long dp[mxn+2][mxn+2][2];
long long mx[mxn+2][mxn+2][2];
long long p[mxn+2][mxn+2];
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y, std::vector<int> W) {
int n = N, m = M;
for (int i=0; i<m; i++) {
int x = X[i], y = Y[i], w = W[i];
p[x+1][y+1] += w;
}
for (int i=0; i<=n; i++) {
partial_sum(p[i], p[i]+n+1, p[i]);
}
for (int j=1; j<=n; j++) dp[0][j][0] = dp[0][j][1] = -1e18;
dp[0][0][0] = dp[0][0][1] = 0;
long long ans = 0;
for (int i=1; i<=n; i++) {
{
long long mx0 = 0;
for (int j=0; j<=n; j++) {
mx0 = max(mx0, (dp[i-1][j][0] - p[i-1][j]));
dp[i][j][0] = max(dp[i][j][0], p[i-1][j] + mx0);
}
}
if (i > 1) {
long long mx0 = 0;
for (int j=0; j<=n; j++) {
mx0 = max(mx0, dp[i-2][j][1]);
dp[i][j][0] = max(dp[i][j][0], mx0 + p[i-1][j]);
}
long long mx1 = 0;
for (int j=n; j>=0; j--) {
mx1 = max(mx1, dp[i-2][j][1] + p[i-1][j]);
dp[i][j][0] = max(dp[i][j][0], mx1);
}
}
{
long long mx1 = 0;
for (int j=n; j>=0; j--) {
mx1 = max(mx1, dp[i-1][j][1] + p[i][j]);
dp[i][j][1] = max(dp[i][j][1], mx1 - p[i][j]);
dp[i][j][1] = max(dp[i][j][1], dp[i][j][0]);
ans = max(ans, dp[i][j][1]);
}
}
}
return ans;
}
