#include "fish.h"
//
#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
#define pb push_back
#define mp make_pair
#define o cout<<"BUG"<<endl;
#define FOR(i, j, n) for(int j = i; j < n; ++j)
#define forn(i, j, n) for(int j = i; j <= n; ++j)
#define nfor(i, j, n) for(int j = n; j >= i; --j)
#define all(v) v.begin(), v.end()
#define ld long double
#define ull unsigned long long
using namespace std;
const int maxn=5000+100,LOG=20,mod=998244353;
int block = 106, timer = 0;
const ld EPS = 1e-18;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define IOS ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define bt(i) (1 << (i))
//#define int ll
const ll inf=2e18;
#define y1 yy
#define prev pre
#define pii pair <int, int>
ll n, a[maxn][maxn], dp[maxn][maxn][2], dp1[maxn], dp2[maxn];
ll pref[maxn][maxn], prefdp[maxn][maxn], prefdp2[maxn][maxn], suffdp[maxn][maxn];
ll max_weights(int N, int m, vector <int> x, vector <int> y, vector <int> c)
{
n = N;
forn(0, i, m-1)
{
a[x[i]+1][y[i]+1] = c[i];
}
forn(1, i, n)
{
forn(1, j, n)
{
pref[i][j] = pref[i][j-1] + a[i][j];
}
}
forn(1, j, n)
{
dp[1][j][0] = 0;
dp[1][j][1] = -inf;
}
dp1[1] = 0;
dp2[1] = 0;
forn(1, j, n)
{
dp[0][j][0] = -inf;
dp[0][j][1] = -inf;
}
suffdp[1][n + 1] = -inf;
nfor(1, j, n)
{
suffdp[1][j] = max(max(dp[1][j][1], dp[1][j][0]) + pref[1+1][j],
suffdp[1][j + 1]);
}
prefdp[1][0] = -inf;
prefdp2[1][0] = -inf;
forn(1, j, n)
{
prefdp2[1][j] = max(prefdp2[1][j - 1], dp[1][j][0] - pref[1][j]);
prefdp[1][j] = max(prefdp[1][j-1], max(dp[1][j][0], dp[1][j][1]));
}
prefdp[0][0] = -inf;
forn(2, i, n)
{
dp1[i] = 0;
forn(1, j, n)
{
dp[i][j][0] = dp2[i-1]+pref[i-1][j];
dp[i][j][0] = max(dp[i][j][0], prefdp2[i-1][j-1] + pref[i-1][j]);
dp[i][j][0] = max(dp[i][j][0], prefdp[i-2][j]+pref[i-1][j]);
dp[i][j][0] = max(dp[i][j][0], suffdp[i-2][j+1]);
dp[i][j][1] = -inf;
dp[i][j][1] = max(dp[i][j][1], suffdp[i - 1][j + 1] - pref[i][j]);
dp1[i] = max(dp1[i], max(dp[i-1][j][1], dp[i-1][j][0]) + pref[i][j]);
// cout << i << " " << j << " " << dp[i][j][0] << " " << dp[i][j][1] << endl;
}
dp2[i] = max(dp2[i - 1], dp1[i - 1]);
suffdp[i][n + 1] = -inf;
nfor(1, j, n)
{
suffdp[i][j] = max(max(dp[i][j][1], dp[i][j][0]) + pref[i+1][j],
suffdp[i][j + 1]);
}
prefdp[i][0] = -inf;
prefdp2[i][0] = -inf;
forn(1, j, n)
{
prefdp2[i][j] = max(prefdp2[i][j - 1], dp[i][j][0] - pref[i][j]);
prefdp[i][j] = max(prefdp[i][j-1], max(dp[i][j][0], dp[i][j][1]));
}
}
ll ans = 0;
forn(1, j, n)
{
ans = max(ans, dp[n][j][0]);
ans = max(ans, dp[n][j][1]);
}
ans = max(ans, dp1[n]);
ans = max(ans, dp2[n]);
return ans;
}
