#include #define ll long long #define pb push_back #define mp make_pair #define pii pair #define pll pair #define all(x) (x).begin(), (x).end() #define fi first #define se second using namespace std; const int nmax = 1005; const int inf = 1 << 30; int n, i, j, sol, a[nmax][nmax], dp[nmax][nmax][4]; int main() { // freopen("test.in", "r", stdin); // freopen("test.out", "w", stdout); scanf("%d", &n); for (i = 1; i <= n; i++) for (j = 1; j <= n; j++) scanf("%d", &a[i][j]); sol = -inf; for (i = 1; i <= n; i++) { for (j = 1; j <= n; j++) { dp[i][j][3] = a[i][j]; if (i > 1) { dp[i][j][3] = max(dp[i][j][3], a[i][j] + dp[i - 1][j][3]); dp[i][j][3] = max(dp[i][j][3], a[i][j] + dp[i - 1][j][1]); } sol = max(sol, dp[i][j][3]); } for (j = 1; j <= n; j++) { dp[i][j][2] = a[i][j]; if (i > 1) { dp[i][j][2] = max(dp[i][j][2], a[i][j] + dp[i - 1][j][2]); dp[i][j][2] = max(dp[i][j][2], a[i][j] + dp[i - 1][j][0]); } sol = max(sol, dp[i][j][2]); } for (j = 1; j <= n; j++) { dp[i][j][0] = a[i][j]; if (j > 1) dp[i][j][0] = max(dp[i][j][0], a[i][j] + dp[i][j - 1][3]); if (j > 1) dp[i][j][0] = max(dp[i][j][0], a[i][j] + dp[i][j - 1][0]); sol = max(sol, dp[i][j][0]); } for (j = n; j >= 1; j--) { dp[i][j][1] = a[i][j]; if (j < n) dp[i][j][1] = max(dp[i][j][1], a[i][j] + dp[i][j + 1][2]); if (j < n) dp[i][j][1] = max(dp[i][j][1], a[i][j] + dp[i][j + 1][1]); sol = max(sol, dp[i][j][1]); } } printf("%d\n", sol); return 0; }