#include <bits/stdc++.h>
using namespace std;
#define MAXN 2005
#define ll long long
#define FOR(i, a, b) for(int i = a; i <= b; ++i)
#define fs first
#define sc second
ll r, s = 0, sfx[18];
short n, g[MAXN][MAXN], k;
int m;
set<pair<ll, pair<pair<short, short>, bool>>> sd;
vector<pair<ll, pair<pair<short, short>, bool>>> d;
vector<int> vct;
bool v[MAXN][MAXN];
void recurse(short itr = 0, short i = -1, ll sm = 0){
if(sm + (sfx[2 * (k - itr)]) < s - r){
return;
}
if(itr == k){
r = min(r, s - sm);
return;
}
FOR(i2, i + 1, m - 1){
if(v[d[i2].sc.fs.fs][d[i2].sc.fs.sc] || v[d[i2].sc.fs.fs + !d[i2].sc.sc][d[i2].sc.fs.sc + d[i2].sc.sc]){
continue;
}
v[d[i2].sc.fs.fs][d[i2].sc.fs.sc] = true;
v[d[i2].sc.fs.fs + !d[i2].sc.sc][d[i2].sc.fs.sc + d[i2].sc.sc] = true;
recurse(itr + 1, i2, sm + d[i2].fs);
v[d[i2].sc.fs.fs][d[i2].sc.fs.sc] = false;
v[d[i2].sc.fs.fs + !d[i2].sc.sc][d[i2].sc.fs.sc + d[i2].sc.sc] = false;
}
}
int main(){
cin >> n >> k;
FOR(i, 1, n) FOR(j, 1, n) {
cin >> g[i][j];
v[i][j] = false;
s += g[i][j];
vct.push_back(g[i][j]);
}
sort(begin(vct), end(vct));
sfx[2*k + 1] = 0;
for(ll i = 2*k; i >= 1; i--) sfx[i] = sfx[i + 1] + vct[vct.size() - 1 - (2*k - i)];
r = s;
FOR(i, 1, n) FOR(j, 1, n) {
if(i != n) {
if(sd.size() < (k - 1) * 7 + 1){
sd.insert({g[i][j] + g[i + 1][j], {{i, j}, 0}});
}else if(g[i][j] + g[i + 1][j] > (*sd.begin()).fs){
sd.erase(*sd.begin());
sd.insert({g[i][j] + g[i + 1][j], {{i, j}, 0}});
}
}
if(j != n) {
if(sd.size() < (k - 1) * 7 + 1){
sd.insert({g[i][j] + g[i][j + 1], {{i, j}, 1}});
}else if(g[i][j] + g[i][j + 1] > (*sd.begin()).fs){
sd.erase(*sd.begin());
sd.insert({g[i][j] + g[i][j + 1], {{i, j}, 1}});
}
}
}
for(auto i : sd) {
d.push_back(i);
}
m = sd.size();
recurse();
cout << r << endl;
}
