#include "fish.h"
#include <bits/stdc++.h>
#define pii pair<int, int>
#define fi first
#define se second
using namespace std;
const int N_MAX = 1e5 + 11;
const int INC = 0;
const int DEC = 1;
const int ZERO = 2;
vector<pair<int, long long>> fish[N_MAX];
int N;
void chmax(long long& x, long long y){
x = max(x, y);
}
map<long long, long long> MSG;
long long id(int x, int y){
return ((long long) x << 32) + y;
}
long long w[5001][5001];
long long g(int x, int y){ // [x, x] times [0, y)
return w[x][y];
}
long long f(int x, int y0, int y1, int y2){ // (x - 1, y1) -> (x, y2) transition
return g(x + 1, y2) + g(x - 1, y2) - g(x, min(y1, y2)) - g(x - 1, min(y2, max(y0, y1)));
}
long long dp[3][5001][5001];
long long max_weights(int N, int M, vector<int> X, vector<int> Y, vector<int> W) {
::N = N;
for(int i = 0; i < M; i++){
fish[X[i]].push_back({Y[i], W[i]});
}
for(int i = 0; i < N; i++){
sort(fish[i].begin(), fish[i].end());
for(int j = 1; j < fish[i].size(); j++){
fish[i][j].se += fish[i][j - 1].se;
}
for(int j = 0; j < fish[i].size(); j++){
w[i][fish[i][j].fi + 1] = fish[i][j].se;
}
for(int j = 1; j <= N; j++){
if(w[i][j] == 0) w[i][j] = w[i][j - 1];
}
}
for(int i = 0; i <= N; i++){
for(int j = 0; j <= N; j++){
dp[0][i][j] = dp[1][i][j] = dp[2][i][j] = -(1LL << 60);
}
}
dp[ZERO][0][0] = 0;
for(int x = 0; x < N; x++){
// ZERO
for(int y = 0; y <= N; y++){
chmax(dp[ZERO][x + 1][y], dp[INC][x][y]);
chmax(dp[ZERO][x + 1][y], dp[DEC][x][y]);
chmax(dp[ZERO][x + 1][0], dp[ZERO][x][y]);
}
// INC
for(int y1 = 0; y1 <= N; y1++){
for(int y2 = y1; y2 <= N; y2++){
chmax(dp[INC][x + 1][y2], dp[INC][x][y1] + g(x + 1, y2) - g(x, y1) + g(x - 1, y2) - g(x - 1, y1));
chmax(dp[INC][x + 1][y2], dp[ZERO][x][y1] + g(x + 1, y2) + g(x - 1, y2) - g(x - 1, min(y2, y1)));
}
}
// DEC
for(int y1 = 0; y1 <= N; y1++){
for(int y2 = 0; y2 <= y1; y2++){
chmax(dp[DEC][x + 1][y2], dp[DEC][x][y1] + g(x + 1, y2) - g(x, y2));
chmax(dp[DEC][x + 1][y2], dp[INC][x][y1] + g(x + 1, y2) - g(x, y2));
}
}
}
/*
for(int k = 0; k < 3; k++){
for(int x = 0; x <= N; x++){
for(int y = 0; y <= N; y++){
cout << dp[k][x][y] << ' ';
}
cout << endl;
}
cout << endl;
}
*/
long long ans = 0;
for(int k = 0; k < 3; k++){
for(int y = 0; y <= N; y++){
ans = max(ans, dp[k][N][y]);
}
}
return ans;
}
