#include <stdio.h>
int INF=-200000000;
int N;
int d[1011][1011];
int cache[1011][1011][3];
int max_(int a, int b) {return a>b?a:b;}
int dp(int y, int x, int pre) {
    if(y<0 || y>=N || x<0 || x>=N) return INF;
    if(y==N-1 && x==N-1) return d[y][x];
    int&ret=cache[y][x][pre];
    if(ret!=101*N*N) return ret;
    ret=0;
    if(y==N-1) {
        return ret=dp(y,x+1,0)+d[y][x];
    } else {
        if(pre==0) { //왼쪽에서 왔다면
            return ret=max_(dp(y+1,x,2),dp(y,x+1,0))+d[y][x];
        } else if(pre==1) { //오른쪽에서 왔다면
            return ret=max_(dp(y+1,x,2),dp(y,x-1,1))+d[y][x];
        } else if(pre==2) { //위에서 왔다면
            ret=max_(dp(y,x+1,0),dp(y,x-1,1))+d[y][x];
            return ret=max_(ret,dp(y+1,x,2)+d[y][x]);
        }
    }
}
int main(void) {
    int i,j,k;
    scanf("%d",&N);
    for(i=0;i<N;i++) for(j=0;j<N;j++) scanf("%d",&d[i][j]);
    for(i=0;i<N;i++) for(j=0;j<N;j++) for(k=0;k<3;k++) cache[i][j][k]=101*N*N;

    int max=dp(1,0,2)+d[0][0];
    int temp=dp(0,1,0)+d[0][0];
    if(max<temp) max=temp;
    printf("%d",max);
    return 0;
}

#include <stdio.h>
int N,K;
int d[222];
int cache[222][222][22];
int dp(int s, int e, int color) {
    int&ret=cache[s][e][color];
    if(ret!=-1) return ret;
    if(s==e) return ret=(d[s]!=color);
    int i,j;
    int temp,min;
    min=0x7fffffff;
    for(i=s;i<e;i++) {
        if(s<=i) temp=dp(s,i,color);
        if(i+1<=e) temp+=dp(i+1,e,color);
        if(min>temp) min=temp;
    }
    for(i=1;i<=K;i++) {
        if(color==i) continue;
        temp=dp(s,e,i)+1;
        if(min>temp) min=temp;
    }
    return ret=min;
}
int main(void) {
    int i,j,k;
    scanf("%d%d",&N,&K);
    for(i=0;i<N;i++) scanf("%d",&d[i]);
    for(i=0;i<=N;i++) for(j=0;j<=N;j++) for(k=0;k<=K;k++) cache[i][j][k]=-1;
    int dap=dp(0,N-1,1);
    int temp;
    for(i=2;i<=K;i++) {
        temp=dp(0,N-1,i);
        if(dap>temp) dap=temp;
    }
    printf("%d",dap);
    return 0;
}