#include<bits/stdc++.h>
typedef int ii;
typedef long long ll;
using namespace std;
const string name = "";
const ii MOD = 1e9 + 7;
const ii N = 2000 + 10;
const ii INF = 1e9 + 237;
ii n, k;
ii a[N][N], nick[N][N];
ii sum = 0;
void INP(){
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
if (fopen((name + ".inp").c_str(),"r")){
freopen((name + ".inp").c_str(),"r",stdin);
freopen((name + ".out").c_str(),"w",stdout);
}
cin >> n >> k;
ii cnt = 0;
for (ii i = 1;i <= n;i++){
for (ii j = 1;j <= n;j++){
cin >> a[i][j];
nick[i][j] = ++cnt;
sum += a[i][j];
}
}
}
struct MCMF{
struct Edge{
ii u, v, capa, cost, flow;
Edge(ii _u, ii _v, ii _capa, ii _cost){
u = _u; v = _v; capa = _capa; cost = _cost; flow = 0;
}
ii res(){
return capa - flow;
}
};
ii Size, s, t;
vector<ii> par, inq, dist;
vector<vector<ii>> e;
vector<Edge> edge;
MCMF(ii Size) : Size(Size) {
s = 0, t = Size - 1;
par.resize(Size);
inq.resize(Size);
dist.resize(Size);
e.resize(Size);
}
void AddEdge(ii u, ii v, ii capa, ii cost){
e[u].push_back(edge.size());
edge.push_back({u, v, capa, cost});
e[v].push_back(edge.size());
edge.push_back({v, u, 0, -cost});
}
bool find_PATH(){
fill(dist.begin(), dist.end(), MOD);
fill(inq.begin(), inq.end(), 0);
queue<ii> q; q.push(s);
ii u, v;
dist[s] = 0;
while(!q.empty()){
u = q.front(); q.pop();
inq[u] = false;
for (ii dir : e[u]){
v = edge[dir].v;
if (dist[v] > dist[u] + edge[dir].cost && edge[dir].res() > 0){
dist[v] = dist[u] + edge[dir].cost;
par[v] = dir;
if (!inq[v]){
inq[v] = true;
q.push(v);
}
}
}
}
return dist[t] != MOD;
}
ll Mincost(ii k){
ll res = 0;
cerr << k << endl;
while(k-- && find_PATH()){
for (ii u = t;u != s;u = edge[par[u]].u){
// cerr << u << " ";
edge[par[u]].flow++;
edge[par[u] ^ 1].flow--;
}
// cerr << s << endl;
// cerr << dist[t] << endl;
res += dist[t];
}
return res;
}
};
ii dx[] = {0, 0, 1, -1},
dy[] = {1, -1, 0, 0};
int main(){
INP();
priority_queue<pair<ii, pair<ii, ii>>> pq;
ii nx, ny;
for (ii i = 1;i <= n;i++){
for (ii j = 1;j <= n;j++){
if ((i + j) & 1){
for (ii dir = 0;dir < 4;dir++){
nx = i + dx[dir];
ny = j + dy[dir];
if (1 <= nx && nx <= n && 1 <= ny && ny <= n){
pq.push({a[i][j] + a[nx][ny], {nick[i][j], nick[nx][ny]}});
}
}
}
}
}
map<ii, ii> mp;
map<ii, bool> mark;
ii cnt = 10;
ii len, u, v, tmp = 0;
MCMF NET(202);
while(!pq.empty() && cnt--){
tie(u, v) = pq.top().second;
len = pq.top().first;
pq.pop();
if (mp[u] == 0) mp[u] = ++tmp;
if (mp[v] == 0) mp[v] = ++tmp;
if (!mark[mp[u]]){
NET.AddEdge(0, mp[u], 1, 0);
mark[mp[u]] = true;
}
if (!mark[mp[v]]){
NET.AddEdge(mp[v], NET.t, 1, 0);
mark[mp[v]] = true;
}
NET.AddEdge(mp[u], mp[v], 1, -len);
// cerr << u << " " << v << "-->" << mp[u] << " " << mp[v] << endl;
// cerr << len << endl;
}
cout << sum + NET.Mincost(k);
return 0;
}
//NGT 1600-2000 cf
//1/200 hard quests
