#include <bits/stdc++.h>
#include "fish.h"
using namespace std;
using ll = long long;
ll t[3001][3001];
ll dp[3001][3001][2];
ll sum[3001][3001];
ll max_weights(int N, int M, vector<int> x, vector<int> y, vector<int> w){
ll ans = 0;
ll pop;
for (int i = 0; i < M; i++){
t[x[i]][y[i]] = w[i];
}
for (int i = 0; i < N; i++){
for (int h = 1; h <= N; h++){
sum[i][h] = t[i][h-1] + sum[i][h-1];
}
if (i){
// CASE 1 a >= b
dp[i][0][1] = dp[i-1][0][1];
ans = max(ans, dp[i][0][1]);
for (int a = 1; a <= N; a++){
dp[i][a][1] = max(dp[i-1][a][1], dp[i][a-1][1] + t[i-1][a-1]);
ans = max(ans, dp[i][a][1]);
}
// CASE 2 b >= a;
dp[i][N][0] = max(dp[i-1][N][0], dp[i-1][N][1]);
ans = max(ans, dp[i][N][0]);
for (int a = N-1; a >= 0; a--){
dp[i][a][0] = max(dp[i][a+1][0] + t[i][a], max(dp[i-1][a][0], dp[i-1][a][1]));
ans = max(ans, dp[i][a][0]);
}
if (i-1){
// CASE 3 min(a,b,c) == b == 0 && a >= c
dp[i][0][1] = max(dp[i][0][1], max(dp[i-2][0][1], dp[i-2][0][0]));
ans = max(ans, dp[i][0][1]);
for (int a = 1; a <= N; a++){
dp[i][a][1] = max(dp[i][a][1], max(dp[i][a-1][1] + t[i-1][a-1], max(dp[i-2][a][0], dp[i-2][a][1]) + sum[i-1][a]));
ans = max(ans, dp[i][a][1]);
}
// CASE 4 min(a,b,c) == b == 0 && c >= a;
dp[i][N][1] = max(dp[i][N][1], max(dp[i-2][N][1], dp[i-2][N][0]) + sum[i-1][N]);
pop = max(dp[i-2][N][1], dp[i-2][N][0]) + sum[i-1][N];
ans = max(ans, dp[i][N][1]);
for (int a = N-1; a >= 0; a--){
dp[i][a][1] = max(dp[i][a][1], max(pop, max(dp[i-2][a][0], dp[i-2][a][1]) + sum[i-1][a]));
pop = max(pop, max(dp[i-2][a][0], dp[i-2][a][1]) + sum[i-1][a]);
ans = max(ans, dp[i][a][1]);
}
}
}
}
return ans;
}
/*
int main(){
int n;
cin >> n;
int m;
cin >> m;
vector<int> x(m);
vector<int> y(m);
vector<int> w(m);
for (int i = 0; i < m; i++){
cin >> x[i];
cin >> y[i];
cin >> w[i];
}
cout << max_weights(n, m, x, y, w);
return 0;
}
*/
