#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
// #define int long long
#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define pb push_back
#define all(a) a.begin(), a.end()
#define endl "\n"
void printVector(vector<int> a){
for (auto x: a) cout << x << " ";
cout << endl;
}
long long max(long long x, long long y){
if (x > y) return x;
else return y;
}
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
std::vector<int> W) {
vector<vector<pair<int, int>>> o(N);
FOR(i,0,M) o[X[i]].pb({Y[i], W[i]});
FOR(i,0,N) sort(all(o[i]));
vector<vector<long long>> dp1(N+1, vector<long long>(N+1)); // when it is currently increasing
vector<vector<long long>> dp2(N+1, vector<long long>(N+1)); // when it is currently decreasing
vector<vector<long long>> prefix(N+1, vector<long long>(N+1));
FOR(i,0,N){
for (auto item: o[i]) prefix[i][item.first] = item.second;
FOR(j,1,N) prefix[i][j] += prefix[i][j-1];
}
long long answer = 0;
FOR(i,1,N){
int c = 0;
FOR(j,0,N){
c = max(c, dp1[i-1][j]-prefix[i-1][j]);
dp1[i][j] = max(dp1[i-1][j], prefix[i-1][j]+c);
}
if (i > 1){ // Case where there is no pier in (i-1)
c = dp2[i-2][N];
FOR(j,0,N){
c = max(c, dp1[i-2][j]);
dp1[i][j] = max(dp1[i][j], prefix[i-1][j]+c);
}
c = 0;
for (int j = N-1; j >= 0; j--){
c = max(c, max(dp1[i-2][j], dp2[i-2][j])+prefix[i-1][j]);
dp1[i][j] = max(dp1[i][j], c);
}
dp1[i][N] = dp1[i-1][N];
}
int d = 0;
FOR(j,0,N){
d = max(d, dp2[i-1][j]+prefix[i][j]);
d = max(d, dp1[i-1][j]+prefix[i][j]);
dp2[i][j] = max(dp2[i][j], d-prefix[i][j]);
}
int u = 0;
FOR(j,0,N) u = max(u, max(dp1[i-1][j], dp2[i-1][j])+prefix[i][j]);
u = max(u, dp2[i-1][N]);
dp2[i][N] = u;
FOR(j,0,N+1) answer = max(answer, dp1[i][j]);
FOR(j,0,N+1) answer = max(answer, dp2[i][j]);
}
return answer;
}
