#include "fish.h"
#include <bits/stdc++.h>
using namespace std;
#define sig signed
#define int long long
#define arr array
#define vec vector
const int N = 3e3 + 5;
int n;
arr<arr<int, N>, N> a;
arr<arr<int, N>, N> sm;
int rng(int i, int l, int r) {
if (l > r) return 0;
return sm[i][r] - sm[i][l - 1];
}
void sm_cmp() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
sm[i][j] = sm[i][j - 1] + a[i][j];
}
}
}
arr<arr<arr<arr<int, 2>, N>, N>, 3> mx;
arr<arr<arr<int, 2>, N>, N> dp;
void slv(int i, int x, int b) {
dp[i][x][b] = rng(i - 1, 1, x);
if (b == 1) {
if (i - 1 >= 1) {
// for (int y = x; y <= n; y++) {
// for (int c : {0, 1}) {
// dp[i][x][b] = max(dp[i][x][b], dp[i - 1][y][c] + sm[i][y] - sm[i][x]);
// }
// }
for (int c : {0, 1}) {
dp[i][x][b] = max(dp[i][x][b], mx[2][i - 1][x][c] - sm[i][x]);
}
}
// cout << i << " " << x << " " << b << ": " << dp[i][x][b] << '\n';
return;
}
if (i - 3 >= 1) {
// for (int y = 1; y <= n; y++) {
// for (int c : {0, 1}) {
// dp[i][x][b] = max(dp[i][x][b], dp[i - 3][y][c] + sm[i - 2][y] + sm[i - 1][x]);
// }
// }
for (int c : {0, 1}) {
dp[i][x][b] = max(dp[i][x][b], mx[2][i - 3][1][c] + sm[i - 1][x]);
}
}
if (i - 2 >= 1) {
// for (int y = x; y <= n; y++) {
// for (int c : {0, 1}) {
// dp[i][x][b] = max(dp[i][x][b], dp[i - 2][y][c] + sm[i - 1][y]);
// }
// }
for (int c : {0, 1}) {
dp[i][x][b] = max(dp[i][x][b], mx[2][i - 2][x][c]);
}
// for (int y = 1; y <= x - 1; y++) {
// for (int c : {0, 1}) {
// dp[i][x][b] = max(dp[i][x][b], dp[i - 2][y][c] + sm[i - 1][x]);
// }
// }
for (int c : {0, 1}) {
dp[i][x][b] = max(dp[i][x][b], mx[0][i - 2][x - 1][c] + sm[i - 1][x]);
}
}
if (i - 1 >= 1) {
// for (int y = 1; y <= x - 1; y++) {
// dp[i][x][b] = max(dp[i][x][b], dp[i - 1][y][0] - sm[i - 1][y] + sm[i - 1][x]);
// }
dp[i][x][b] = max(dp[i][x][b], mx[1][i - 1][x - 1][0] + sm[i - 1][x]);
}
// cout << i << " " << x << " " << b << ": " << dp[i][x][b] << '\n';
}
void dp_cmp() {
for (int i = 1; i <= n; i++) {
for (int x = 1; x <= n; x++) {
for (int b : {0, 1}) {
slv(i, x, b);
}
}
for (int x = 1; x <= n; x++) {
for (int b : {0, 1}) {
mx[0][i][x][b] = max(mx[0][i][x - 1][b], dp[i][x][b]);
mx[1][i][x][b] = max(mx[1][i][x - 1][b], dp[i][x][b] - sm[i][x]);
}
}
for (int x = n; x >= 1; x--) {
for (int b : {0, 1}) {
mx[2][i][x][b] = max(mx[2][i][x + 1][b], dp[i][x][b] + sm[i + 1][x]);
}
}
}
}
int max_weights(sig _n, sig _m, vec<sig> _x, vec<sig> _y, vec<sig> _w) {
n = _n;
for (int i = 0; i < _m; i++) a[_x[i] + 1][_y[i] + 1] = _w[i];
sm_cmp();
dp_cmp();
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int x = 1; x <= n; x++) {
for (int b : {0, 1}) {
ans = max(ans, dp[i][x][b] + rng(i + 1, 1, x));
}
}
}
return ans;
}
