#include <algorithm>#include <iostream>#include <cstring>#include <string>#include <vector>#include <bitset>#include <cstdio>#include <queue>#include <stack>#include <cmath>#include <list>#include <map>#include <set>#define pk(x) printf("%d\n", x)using namespace std;#define PI acos(-1.0)#define EPS 1E-6#define clr(x,c) memset(x,c,sizeof(x))//#pragma comment(linker, "/STACK:102400000,102400000")typedef long long ll;const int MAXV = 2000;const int INF = 1<<30;struct Edge { int to, cap, cost, rev; };vector<Edge> G[MAXV];int dist[MAXV], prv[MAXV], pre[MAXV], in[MAXV];queue<int> que;void addedge(int from, int to, int cap, int cost) {    G[from].push_back((Edge){to, cap, cost, G[to].size()});    G[to].push_back((Edge){from, 0, -cost, G[from].size()-1});}int min_cost_max_flow(int s, int t) { //, int f) {    int res = 0;    int f = 0;    while (1) { //f > 0) {        for (int i = 1; i <= t; ++i) dist[i] = INF, in[i] = 0;        dist[s] = 0;        while (!que.empty()) que.pop();        in[s] = 1;        que.push(s);        while (!que.empty()) {            int u = que.front(); que.pop(); in[u] = 0;            for (int i = 0; i < G[u].size(); ++i) {                Edge &e = G[u][i];                if (e.cap > 0 && dist[e.to] > dist[u] + e.cost) {                    dist[e.to] = dist[u] + e.cost;                    prv[e.to] = u;                    pre[e.to] = i;                    if (in[e.to] == 0) {                        in[e.to] = 1;                        que.push(e.to);                    }                }            }        }        if (dist[t] == INF) break; //return -1;        int d = INF; // d = f;        for (int v = t; v != s; v = prv[v]) {            d = min(d, G[prv[v]][pre[v]].cap);        }        f += d;        res += d * dist[t];        for (int v = t; v != s; v = prv[v]) {            Edge &e = G[prv[v]][pre[v]];            e.cap -= d;            G[v][e.rev].cap += d;        }    }    return res;    //return f;}int n;int getid1(int x, int y) { return x*n+y+1; }int getid2(int x, int y) { return x*n+y+n*n+1; }int a[30][30];int main(){    while (~scanf("%d", &n)) {        for (int i = 0; i < n; ++i) {            for (int j = 0; j < n; ++j) {                scanf("%d", &a[i][j]);            }        }        for (int i = 0; i <= 2*n*n; ++i) G[i].clear();        for (int i = 0; i < n; ++i) {            for (int j = 0; j < n; ++j) {                if (i+j == 0) addedge(getid1(i,j), getid2(i,j), 2, -a[i][j]);                else if (i+j == n*2 - 2) addedge(getid1(i,j), getid2(i, j), 2, -a[i][j]);                else addedge(getid1(i, j), getid2(i, j), 1, -a[i][j]);                if (i+1<n) addedge(getid2(i, j), getid1(i+1, j), 1, 0);                if (j+1<n) addedge(getid2(i, j), getid1(i, j+1), 1, 0);            }        }        printf("%d\n", -min_cost_max_flow(getid1(0,0), getid2(n-1,n-1)) - a[0][0] - a[n-1][n-1]);    }    return 0;}

#include <algorithm>#include <iostream>#include <cstring>#include <string>#include <vector>#include <bitset>#include <cstdio>#include <queue>#include <stack>#include <cmath>#include <list>#include <map>#include <set>#define pk(x) printf("%d\n", x)using namespace std;#define PI acos(-1.0)#define EPS 1E-6#define clr(x,c) memset(x,c,sizeof(x))//#pragma comment(linker, "/STACK:102400000,102400000")typedef long long ll;const int MAXV = 610*610*2+2;const int INF = 1<<30;struct Edge { int to, cap, cost, rev; };vector<Edge> G[MAXV];int dist[MAXV], prv[MAXV], pre[MAXV], in[MAXV];queue<int> que;void addedge(int from, int to, int cap, int cost) {    G[from].push_back((Edge){to, cap, cost, G[to].size()});    G[to].push_back((Edge){from, 0, -cost, G[from].size()-1});}int min_cost_max_flow(int s, int t) { //, int f) {    int res = 0;    int f = 0;    while (1) { //f > 0) {        for (int i = 1; i <= t; ++i) dist[i] = INF, in[i] = 0;        dist[s] = 0;        while (!que.empty()) que.pop();        in[s] = 1;        que.push(s);        while (!que.empty()) {            int u = que.front(); que.pop(); in[u] = 0;            for (int i = 0; i < G[u].size(); ++i) {                Edge &e = G[u][i];                if (e.cap > 0 && dist[e.to] > dist[u] + e.cost) {                    dist[e.to] = dist[u] + e.cost;                    prv[e.to] = u;                    pre[e.to] = i;                    if (in[e.to] == 0) {                        in[e.to] = 1;                        que.push(e.to);                    }                }            }        }        if (dist[t] == INF) break; //return -1;        int d = INF; // d = f;        for (int v = t; v != s; v = prv[v]) {            d = min(d, G[prv[v]][pre[v]].cap);        }        f += d;        res += d * dist[t];        for (int v = t; v != s; v = prv[v]) {            Edge &e = G[prv[v]][pre[v]];            e.cap -= d;            G[v][e.rev].cap += d;        }    }    return res;    //return f;}inline int Scan(){    char ch = getchar();    int data = http://www.mamicode.com/0;    while (ch < ‘0‘ || ch > ‘9‘) ch = getchar();    do {        data = data*10 + ch-‘0‘;        ch = getchar();    } while (ch >= ‘0‘ && ch <= ‘9‘);    return data;}int n;int getid1(int x, int y) { return x*n+y+1; }int getid2(int x, int y) { return x*n+y+n*n+1; }int a[600][600];int main(){    while (~scanf("%d", &n)) {        int maxn = 2*n*n;        for (int i = 0; i <= maxn; ++i) G[i].clear();        for (int i = 0; i < n; ++i) {            for (int j = 0; j < n; ++j) {                a[i][j] = Scan();                if (i+j == 0 || i+j == n*2-2) addedge(getid1(i,j), getid2(i,j), 2, -a[i][j]);                else addedge(getid1(i, j), getid2(i, j), 1, -a[i][j]);                if (i+1<n) addedge(getid2(i, j), getid1(i+1, j), 1, 0);                if (j+1<n) addedge(getid2(i, j), getid1(i, j+1), 1, 0);            }        }        printf("%d\n", -min_cost_max_flow(getid1(0,0), getid2(n-1,n-1)) - a[0][0] - a[n-1][n-1]);    }    return 0;}