#include "fish.h"
#include "bits/stdc++.h"
using namespace std;
#ifndef EVAL
#include "grader.cpp"
#endif
#define ar array
typedef int32_t ii;
typedef long long ll;
#define int ll
/*
5 4
0 2 5
1 1 2
4 4 1
3 3 3
*/
int max_weights(ii n, ii m, vector<ii> x, vector<ii> y, vector<ii> w) {
vector<vector<int>> a(n + 1, vector<int>(n + 1));
for(int i=0;i<m;i++){
x[i]++, y[i]++;
a[x[i]][y[i]] = w[i];
}
vector<vector<ar<int, 2>>> dp(n + 1, vector<ar<int, 2>>(n + 1, {0, 0}));
vector<vector<int>> pref(n + 1, vector<int>(n + 1));
vector<vector<int>> tp(n + 1, vector<int>(n + 1));
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
pref[i][j] = pref[i][j-1] + a[i][j];
}
}
vector<int> pref_tp(n + 1), suff_tp(n + 2), pref_00(n + 1), suff_11(n + 2), suff_01(n + 2);
vector<int> mx(n + 1);
/*
5 4
0 2 5
1 1 2
4 4 1
3 3 3
*/
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
dp[i][j][0] = pref[i - 1][j];
if(3 <= i) dp[i][j][0] += mx[i - 3];
for(int k=1;k<=n;k++){
if(1 < i && k <= j){
dp[i][j][0] = max(dp[i][j][0], dp[i - 1][k][0] - pref[i - 1][k] + pref[i - 1][j]);
}
if(2 < i){
dp[i][j][0] = max(dp[i][j][0], tp[i - 2][k] + pref[i - 1][max(j, k)]);
}
if(1 < i && j <= k){
dp[i][j][1] = max(dp[i][j][1], dp[i - 1][k][1] + pref[i][k] - pref[i][j]);
if(j < k){
dp[i][j][1] = max(dp[i][j][1], dp[i - 1][k][0] + pref[i][k] - pref[i][j]);
}
}
}
ar<int, 2> tmp {};
if(i < 1){
//~ dp[i][j][0] = max(dp[i][j][0], pref_00[j] + pref[i - 1][j]);
//~ dp[i][j][1] = max(dp[i][j][1], suff_11[j] - pref[i][j]);
//~ dp[i][j][1] = max(dp[i][j][1], suff_01[j + 1] - pref[i][j]);
tmp[0] = max(tmp[0], pref_00[j] + pref[i - 1][j]);
tmp[1] = max(tmp[1], suff_11[j] - pref[i][j]);
tmp[1] = max(tmp[1], suff_01[j + 1] - pref[i][j]);
}
if(i < 2){
tmp[0] = max(tmp[0], pref_tp[j] + pref[i - 1][j]);
tmp[0] = max(tmp[0], suff_tp[j]);
tmp[0] = max(tmp[0], pref_tp[j] + pref[i - 1][j]);
tmp[0] = max(tmp[0], suff_tp[j]);
}
assert(tmp[0] == dp[i][j][0]);
tp[i][j] = max(dp[i][j][0], dp[i][j][1]);
mx[i] = max(mx[i], tp[i][j]);
}
if(i < n){
for(int j=1;j<=n;j++){
mx[i] = max(mx[i], tp[i][j] + pref[i + 1][j]);
if(i > 1){
pref_tp[j] = max(pref_tp[j - 1], tp[i - 1][j]);
}
pref_00[j] = max(pref_00[j - 1], dp[i][j][0] - pref[i][j]);
}
for(int j=n;j>0;j--){
if(i > 1){
suff_tp[j] = max(suff_tp[j + 1], tp[i - 1][j] + pref[i][j]);
}
suff_11[j] = max(suff_11[j + 1], dp[i][j][1] + pref[i + 1][j]);
suff_01[j] = max(suff_01[j + 1], dp[i][j][0] + pref[i + 1][j]);
}
}
mx[i] = max(mx[i-1], mx[i]);
}
return mx[n];
}
