#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using pll = pair < ll, ll >;
using pal = pair < pll ,pll > ;
ll a[2002][2002];
int main() {
ll n, m, r, k, can, p, x, s, y, i, j, ans =0, t, sum;
cin >> n >> k;
sum = 0;
priority_queue < pal ,vector < pal>, greater < pal > > pq;
for ( i = 1; i <= n; i ++) {
for (j = 1; j <= n; j ++){
cin >> a[i][j];
sum += a[i][j];
}
}
for (i = 1; i <= n; i ++) {
for (j = 1; j < n; j ++) {
r = a[i][j] + a[i][j + 1];
pq.push(make_pair(make_pair(r, 1), make_pair(i, j)));
if ( pq.size() > 8 * k) pq.pop();
}
}
for (i = 1; i < n; i ++) {
for (j = 1; j <= n; j ++) {
r = a[i][j] + a[i + 1][j];
pq.push(make_pair(make_pair(r, 0), make_pair(i, j)));
if ( pq.size() > 8 * k) pq.pop();
}
}
vector < pair < pll, pll > > v;
while(!pq.empty()) {
auto R = pq.top();
pq.pop();
v.push_back(R);
}
ll R= v.size();
for (i = 0; i < (1<<R); i ++) {
vector < pair < pll, pll > > q;
if (__builtin_popcount(i) != k) {
continue;
}
for (j = 0; j < R; j ++) {
p = i & (1<< j);
if ( p != 0) {
q.push_back(v[j]);
}
}
can = 1;
s = 0;
pll N_1, N_2, N_3, N_4;
for (j = 0; j < q.size(); j ++) {
N_1 = q[j].second;
N_2 = N_1;
if ( q[j].first.second == 0) N_2.first ++;
else N_2.second ++;
s += a[N_1.first][N_1.second];
s += a[N_2.first][N_2.second];
for ( r = j + 1; r < q.size(); r ++) {
N_3 = q[r].second;
N_4 = N_3;
if ( q[r].first.second == 0) N_4.first ++;
else N_4.second ++;
if ( N_1 == N_2 || N_1 == N_3 || N_1 == N_4 || N_2 == N_3 || N_2 == N_4 || N_3 == N_4) {
can =0;
break;
}
}
}
if ( can == 1) {
ans = max(ans, s);
}
}
cout<< sum - ans << endl;
}
