#include <stdio.h>
 
const int MAX   = 50;
const int MAX_D = 4;
const int DOWN = 0, LEFT = 1, RIGHT = 2;
 
int G[MAX][MAX];
int M[MAX][MAX][MAX * MAX][3];
int n, m;
 
int max (int a, int b) { return a > b ? a : b; }
 
int f(int i, int j, int p, int d) {
        if (i == n || j == n || j < 0 || p == m)
                return 0;
        if (M[i][j][p][d] != -1) 
                return M[i][j][p][d];
 
        //We can always move down
        int ret = f(i + 1, j, p + 1, DOWN);
        //We have to check if we have enough steps to move sideways
        if((m-p) > (n-i)) {
                if(d == DOWN || d == RIGHT)
                        ret = max(ret, f(i, j + 1, p + 1, RIGHT));
                if(d == DOWN || d == LEFT)
                        ret = max(ret, f(i, j - 1, p + 1, LEFT));
        }
        return M[i][j][p][d] = ret + G[i][j];
}               
 
int main()
{
        for (int i = 0; i < MAX; i++) {
                for (int j = 0; j < MAX; j++) {
                        for (int p = 0; p < MAX * MAX; p++)
                                for (int d = 0; d < MAX_D; d++)
                                        M[i][j][p][d] = -1;
                        G[i][j] = 0;
                }
        }
 
        scanf ("%d %d", &n, &m);
        for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                        scanf ("%d", &G[i][j]);
 
        printf ("%d\n", f(0, 0, 0, DOWN));
        return 0;
}

I2luY2x1ZGUgPHN0ZGlvLmg+CiAKY29uc3QgaW50IE1BWCAgID0gNTA7CmNvbnN0IGludCBNQVhfRCA9IDQ7CmNvbnN0IGludCBET1dOID0gMCwgTEVGVCA9IDEsIFJJR0hUID0gMjsKIAppbnQgR1tNQVhdW01BWF07CmludCBNW01BWF1bTUFYXVtNQVggKiBNQVhdWzNdOwppbnQgbiwgbTsKIAppbnQgbWF4IChpbnQgYSwgaW50IGIpIHsgcmV0dXJuIGEgPiBiID8gYSA6IGI7IH0KIAppbnQgZihpbnQgaSwgaW50IGosIGludCBwLCBpbnQgZCkgewogICAgICAgIGlmIChpID09IG4gfHwgaiA9PSBuIHx8IGogPCAwIHx8IHAgPT0gbSkKICAgICAgICAgICAgICAgIHJldHVybiAwOwogICAgICAgIGlmIChNW2ldW2pdW3BdW2RdICE9IC0xKSAKICAgICAgICAgICAgICAgIHJldHVybiBNW2ldW2pdW3BdW2RdOwoKICAgICAgICAvL1dlIGNhbiBhbHdheXMgbW92ZSBkb3duCiAgICAgICAgaW50IHJldCA9IGYoaSArIDEsIGosIHAgKyAxLCBET1dOKTsKICAgICAgICAvL1dlIGhhdmUgdG8gY2hlY2sgaWYgd2UgaGF2ZSBlbm91Z2ggc3RlcHMgdG8gbW92ZSBzaWRld2F5cwogICAgICAgIGlmKChtLXApID4gKG4taSkpIHsKICAgICAgICAgICAgICAgIGlmKGQgPT0gRE9XTiB8fCBkID09IFJJR0hUKQogICAgICAgICAgICAgICAgICAgICAgICByZXQgPSBtYXgocmV0LCBmKGksIGogKyAxLCBwICsgMSwgUklHSFQpKTsKICAgICAgICAgICAgICAgIGlmKGQgPT0gRE9XTiB8fCBkID09IExFRlQpCiAgICAgICAgICAgICAgICAgICAgICAgIHJldCA9IG1heChyZXQsIGYoaSwgaiAtIDEsIHAgKyAxLCBMRUZUKSk7CiAgICAgICAgfQogICAgICAgIHJldHVybiBNW2ldW2pdW3BdW2RdID0gcmV0ICsgR1tpXVtqXTsKfSAgICAgICAgICAgICAgIAogCmludCBtYWluKCkKewogICAgICAgIGZvciAoaW50IGkgPSAwOyBpIDwgTUFYOyBpKyspIHsKICAgICAgICAgICAgICAgIGZvciAoaW50IGogPSAwOyBqIDwgTUFYOyBqKyspIHsKICAgICAgICAgICAgICAgICAgICAgICAgZm9yIChpbnQgcCA9IDA7IHAgPCBNQVggKiBNQVg7IHArKykKICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBmb3IgKGludCBkID0gMDsgZCA8IE1BWF9EOyBkKyspCiAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICAgICBNW2ldW2pdW3BdW2RdID0gLTE7CiAgICAgICAgICAgICAgICAgICAgICAgIEdbaV1bal0gPSAwOwogICAgICAgICAgICAgICAgfQogICAgICAgIH0KICAgICAgICAKICAgICAgICBzY2FuZiAoIiVkICVkIiwgJm4sICZtKTsKICAgICAgICBmb3IgKGludCBpID0gMDsgaSA8IG47IGkrKykKICAgICAgICAgICAgICAgIGZvciAoaW50IGogPSAwOyBqIDwgbjsgaisrKQogICAgICAgICAgICAgICAgICAgICAgICBzY2FuZiAoIiVkIiwgJkdbaV1bal0pOwogICAgICAgICAgICAgICAgICAgICAgICAKICAgICAgICBwcmludGYgKCIlZFxuIiwgZigwLCAwLCAwLCBET1dOKSk7CiAgICAgICAgcmV0dXJuIDA7Cn0=

MyA1CjEgMSAzMAoxIDEgMQoxIDEgMQ==

3 5
1 1 30
1 1 1
1 1 1