#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;
#define re(i, n) for (int i=0; i<n; i++)
#define re1(i, n) for (int i=1; i<=n; i++)
#define re2(i, l, r) for (int i=l; i<r; i++)
#define re3(i, l, r) for (int i=l; i<=r; i++)
#define rre(i, n) for (int i=n-1; i>=0; i--)
#define rre1(i, n) for (int i=n; i>0; i--)
#define rre2(i, r, l) for (int i=r-1; i>=l; i--)
#define rre3(i, r, l) for (int i=r; i>=l; i--)
const int MAXN = 20, MAXM = 101, INF = ~0U >> 2;
int n0, n, m, A0[MAXN][MAXN], A[2][MAXN][MAXN], U[2][MAXN], D[2][MAXN], L[2][MAXN], R[2][MAXN], S[2][MAXN], F[2][MAXM];
int x0, y0, x1, y1, tmp[MAXN], res = -INF;
void init()
{
scanf("%d%d", &n0, &m); n = n0 << 1;
re(i, n) re(j, n) scanf("%d", &A0[i][j]);
}
void prepare()
{
int x, y; re(i, n) re(j, n) A[0][i][j] = A[1][i][j] = -INF;
re(i, n) re(j, n) {
x = i + j; y = i - j;
if (x & 1) A[1][x >> 1][y + n >> 1] = A0[i][j]; else A[0][x >> 1][(y + n >> 1) - 1] = A0[i][j];
}
re(i, n) {
re(j, n) if (A[0][j][i] != -INF) {U[0][i] = j; break;}
rre(j, n) if (A[0][j][i] != -INF) {D[0][i] = j; break;}
re(j, n) if (A[0][i][j] != -INF) {L[0][i] = j; break;}
rre(j, n) if (A[0][i][j] != -INF) {R[0][i] = j; break;}
S[0][i] = 0; re(j, n) if (A[0][i][j] != -INF) S[0][i] += A[0][i][j];
}
re(i, n) {
re(j, n) if (A[1][j][i] != -INF) {U[1][i] = j; break;}
rre(j, n) if (A[1][j][i] != -INF) {D[1][i] = j; break;}
re(j, n) if (A[1][i][j] != -INF) {L[1][i] = j; break;}
rre(j, n) if (A[1][i][j] != -INF) {R[1][i] = j; break;}
S[1][i] = 0; re(j, n) if (A[1][i][j] != -INF) S[1][i] += A[1][i][j];
}
re(i, n) F[0][i] = F[1][i] = -INF;
if (n0 & 1) {
x0 = n0 - 1 >> 1; y0 = (n0 + 1 >> 1) - 1;
x1 = y1 = n0 >> 1;
} else {
x0 = n0 >> 1; y0 = x0 - 1;
x1 = n0 - 1 >> 1; y1 = n0 + 1 >> 1;
}
F[0][0] = 0;
re3(i, U[0][y0], D[0][y0]) {if (i != x0) F[0][0] += A[0][i][y0]; S[0][i] -= A[0][i][y0];}
re(i, n) if (i != y0 && A[0][x0][i] != -INF) F[0][0] += A[0][x0][i];
F[1][0] = 0;
re3(i, U[1][y1], D[1][y1]) {if (i != x1) F[1][0] += A[1][i][y1]; S[1][i] -= A[1][i][y1];}
re(i, n) if (i != y1 && A[1][x1][i] != -INF) F[1][0] += A[1][x1][i];
}
void dfs0(int dep, int v, int sum0, int KK, int SKKL, int SKKR)
{
if (v > m) return;
if (dep == n - 1) {
int sum = sum0 + F[0][0] + A[0][x0][y0], len;
if (U[0][KK] > U[0][y0]) {
int sum1;
re3(i, U[0][KK], D[0][KK]) {
sum1 = sum + S[0][i]; len = 0; if (sum1 > F[0][v + 1]) F[0][v + 1] = sum1;
re(j, n) if (j != x0 && j != i && (SKKL >= L[0][j] || SKKR <= R[0][j])) tmp[len++] = S[0][j];
sort(tmp, tmp + len);
rre(j, len) {sum1 += tmp[j]; if (sum1 > F[0][v + 1 + len - j]) F[0][v + 1 + len - j] = sum1;}
}
} else {
if (v && sum > F[0][v]) F[0][v] = sum;
len = 0; re(i, n) if (i != x0 && (SKKL >= L[0][i] || SKKR <= R[0][i])) tmp[len++] = S[0][i];
sort(tmp, tmp + len);
rre(i, len) {sum += tmp[i]; if (sum > F[0][v + len - i]) F[0][v + len - i] = sum;}
}
} else if (dep == y0) dfs0(dep + 1, v, sum0, KK, SKKL, SKKR); else {
int sum1 = sum0, SKKL0, SKKR0;
re3(i, U[0][dep], D[0][dep]) if (i != x0) {sum1 += A[0][i][dep]; S[0][i] -= A[0][i][dep];}
if (dep < n0 && dep > SKKL) SKKL0 = dep; else SKKL0 = SKKL;
if (dep >= n0 - 1 && dep < SKKR) SKKR0 = dep; else SKKR0 = SKKR;
dfs0(dep + 1, v + 1, sum1, U[0][KK] >= U[0][dep] ? KK : dep, SKKL0, SKKR0);
re3(i, U[0][dep], D[0][dep]) if (i != x0) S[0][i] += A[0][i][dep];
dfs0(dep + 1, v, sum0, KK, SKKL, SKKR);
}
}
void dfs1(int dep, int v, int sum0, int KK, int SKKL, int SKKR)
{
if (v > m) return;
if (dep == n) {
int sum = sum0 + F[1][0] + A[1][x1][y1], len;
if (U[1][KK] > U[1][y1]) {
int sum1;
re3(i, U[1][KK], D[1][KK]) {
sum1 = sum + S[1][i]; len = 0; if (sum1 > F[1][v + 1]) F[1][v + 1] = sum1;
re(j, n-1) if (j != x1 && j != i && (SKKL >= L[1][j] || SKKR <= R[1][j])) tmp[len++] = S[1][j];
sort(tmp, tmp + len);
rre(j, len) {sum1 += tmp[j]; if (sum1 > F[1][v + 1 + len - j]) F[1][v + 1 + len - j] = sum1;}
}
} else {
if (v && sum > F[1][v]) F[1][v] = sum;
len = 0; re(i, n-1) if (i != x1 && (SKKL >= L[1][i] || SKKR <= R[1][i])) tmp[len++] = S[1][i];
sort(tmp, tmp + len);
rre(i, len) {sum += tmp[i]; if (sum > F[1][v + len - i]) F[1][v + len - i] = sum;}
}
} else if (dep == y1) dfs1(dep + 1, v, sum0, KK, SKKL, SKKR); else {
int sum1 = sum0, SKKL0, SKKR0;
re3(i, U[1][dep], D[1][dep]) if (i != x1) {sum1 += A[1][i][dep]; S[1][i] -= A[1][i][dep];}
if (dep < n0 && dep > SKKL) SKKL0 = dep; else SKKL0 = SKKL;
if (dep >= n0 && dep < SKKR) SKKR0 = dep; else SKKR0 = SKKR;
dfs1(dep + 1, v + 1, sum1, U[1][KK] >= U[1][dep] ? KK : dep, SKKL0, SKKR0);
re3(i, U[1][dep], D[1][dep]) if (i != x1) S[1][i] += A[1][i][dep];
dfs1(dep + 1, v, sum0, KK, SKKL, SKKR);
}
}
void solve()
{
dfs0(0, 0, 0, y0, y0<n0?y0:-INF, y0>=n0-1?y0:INF);
dfs1(0, 0, 0, y1, y1<n0?y1:-INF, y1>=n0?y1:INF);
re(x, 2) re2(i, 2, MAXM) if (F[x][i - 1] > F[x][i]) F[x][i] = F[x][i - 1];
re3(i, 0, m) if (F[0][i] + F[1][m - i] > res) res = F[0][i] + F[1][m - i];
}
void pri()
{
printf("%d\n", res);
}
int main()
{
init();
prepare();
solve();
pri();
return 0;
}