#include "fish.h"
#include <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
#define pb push_back
using namespace std;
typedef pair<ll,ll> pii;
typedef pair<ll,pii> ipii;
const int MAXN = 5010;
const int MAXA = 3e5+10;
const ll INF = 2e15+10;
void chmx(auto &a, auto b){ a = max(a, b); }
void chmn(auto &a, auto b){ a = min(a, b); }
int n, m;
ll x[MAXA], y[MAXA], w[MAXA], a[MAXN][MAXN];
ll up[MAXN][MAXN], dw[MAXN][MAXN], pr[MAXN][MAXN];
long long max_weights(int N, int M, std::vector<int> X, std::vector<int> Y,
std::vector<int> W) {
n = N; m = M;
for(int i=1; i<=m; i++){
x[i] = X[i-1]+1; y[i] = Y[i-1]+1; w[i] = W[i-1];
a[x[i]][y[i]] += w[i];
}
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++) pr[i][j] = pr[i][j-1]+a[i][j];
}
for(int i=0; i<=n; i++)
for(int j=0; j<=n; j++) dw[i][j] = up[i][j] = -INF;
dw[0][0] = up[0][0] = 0;
ll ANS = 0;
for(int i=1; i<=n; i++){
for(int j=0; j<=n; j++){
for(int k=0; k<=j; k++){
chmx(up[i][j], up[i-1][k] + pr[i-1][j]-pr[i-1][k] );
}
for(int k=j; k<=n; k++){
chmx(dw[i][j], dw[i-1][k] + pr[i][k]-pr[i][j] );
}
}
ll MX = 0;
for(int j=0; j<=n; j++) chmx(MX, max(dw[i-1][j], up[i-1][j]));
chmx(up[i][0], MX);
chmx(dw[i][0], MX);
for(int j=0; j<=n; j++){
// if(i>=2){
// ll ba = 0;
// for(int k=0; k<=n; k++)
// chmx(ba, max(up[i-2][k], dw[i-2][k]));
// for(int j=0; j<=n; j++){
// chmx(up[i][j], ba + cost(i-1, 1, j));
// chmx(dw[i][j], ba + cost(i-1, 1, j));
// }
// }
chmx(dw[i][j], up[i][j]);
chmx(ANS, up[i][j]);
chmx(ANS, dw[i][j]);
}
}
return ANS;
}
