#include <bits/stdc++.h>
#define FNAME "test"
using namespace std;
template<typename T> using min_heap = priority_queue<T,vector<T>,greater<T>>;
template<class X, class Y>
bool minimize(X& x, const Y& y) {
if (x > y) {
x = y;
return true;
}
return false;
}
template<class Cost, class Flow>
class MinCostFlow {
private:
struct Edge {
int from, to;
Flow capa, flow;
Cost cost;
Edge(int _from, int _to, Flow _capa, Cost _cost) {
from = _from; to = _to;
capa = _capa; flow = Flow(0);
cost = _cost;
}
Flow residual() const {
return capa - flow;
}
};
int numNode;
vector<Edge> edges;
vector<vector<int>> adj;
vector<Cost> dist;
vector<int> par;
vector<bool> inQueue;
bool fordBellman(int source, int sink) {
fill(dist.begin(), dist.end(), numeric_limits<Cost>::max());
fill(par.begin(), par.end(), -1);
fill(inQueue.begin(), inQueue.end(), false);
queue<int> q;
dist[source] = 0; q.push(source); inQueue[source] = true;
while (!q.empty()) {
int u = q.front(); q.pop(); inQueue[u] = false;
for (int edgeID : adj[u]) if (edges[edgeID].residual() > Flow(0)) {
int v = edges[edgeID].to;
Cost cost = edges[edgeID].cost;
if (minimize(dist[v], dist[u] + cost)) {
par[v] = edgeID;
if (!inQueue[v]) {
q.push(v);
inQueue[v] = true;
}
}
}
}
return dist[sink] < numeric_limits<Cost>::max();
}
public:
MinCostFlow(int _numNode = 0) {
numNode = _numNode;
edges.clear();
adj.assign(_numNode, vector<int>());
dist.assign(_numNode, Cost(0));
par.assign(_numNode, -1);
inQueue.assign(_numNode, false);
}
void addEdge(int from, int to, Flow capa, Cost cost) {
adj[from].push_back(edges.size());
edges.push_back(Edge(from, to, capa, cost));
adj[to].push_back(edges.size());
edges.push_back(Edge(to, from, Flow(0), -cost));
}
pair<Cost,Flow> getMCMF(int source, int sink, Flow desiredFlow = numeric_limits<Flow>::max()) {
Cost totalCost = Cost(0);
Flow totalFlow = Flow(0);
while (fordBellman(source, sink) && totalFlow < desiredFlow) {
Flow delta = desiredFlow - totalFlow;
for (int node = sink; node != source; node = edges[par[node]].from)
minimize(delta, edges[par[node]].residual());
totalFlow += delta;
totalCost += dist[sink] * Cost(delta);
for (int node = sink; node != source; node = edges[par[node]].from) {
edges[par[node]].flow += delta;
edges[par[node] ^ 1].flow -= delta;
}
}
if (desiredFlow != numeric_limits<Flow>::max()) {
if (totalFlow != desiredFlow) {
totalFlow = -1;
}
}
return make_pair(totalCost, totalFlow);
}
};
void Task() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
if (fopen(FNAME".inp","r")) {
freopen(FNAME".inp","r",stdin);
freopen(FNAME".out","w",stdout);
}
}
void Solve() {
int tableSize, numDomino;
cin >> tableSize >> numDomino;
vector<vector<int>> grid(tableSize, vector<int>(tableSize));
for (int row = 0; row < tableSize; ++row) {
for (int col = 0; col < tableSize; ++col) {
cin >> grid[row][col];
}
}
auto cellID = [&](int row, int col) -> int {
return row * tableSize + col;
};
min_heap<pair<int,pair<int,int>>> pq;
int ans = 0;
for (int row = 0; row < tableSize; ++row) {
for (int col = 0; col < tableSize; ++col) {
ans += grid[row][col];
if ((row + col) % 2 == 1) continue;
if (row - 1 >= 0) {
int cost = -(grid[row][col] + grid[row - 1][col]);
pq.push({cost, {cellID(row,col), cellID(row - 1, col)}});
}
if (row + 1 < tableSize) {
int cost = -(grid[row][col] + grid[row + 1][col]);
pq.push({cost, {cellID(row,col), cellID(row + 1, col)}});
}
if (col - 1 >= 0) {
int cost = -(grid[row][col] + grid[row][col - 1]);
pq.push({cost, {cellID(row,col), cellID(row, col - 1)}});
}
if (col + 1 < tableSize) {
int cost = -(grid[row][col] + grid[row][col + 1]);
pq.push({cost, {cellID(row,col), cellID(row, col + 1)}});
}
}
}
int numNeed = min(8 * numDomino, (int) pq.size());
vector<pair<int,pair<int,int>>> edges;
for (int i = 1; i <= numNeed; ++i) {
edges.push_back(pq.top());
pq.pop();
}
vector<int> vec;
for (auto e : edges) {
vec.push_back(e.second.first);
vec.push_back(e.second.second);
}
sort(vec.begin(), vec.end());
vec.resize(unique(vec.begin(), vec.end()) - vec.begin());
int numNode = (int) vec.size() + 2;
vector<int> halfA, halfB;
for (auto& e : edges) {
e.second.first = lower_bound(vec.begin(), vec.end(), e.second.first) - vec.begin() + 1;
halfA.push_back(e.second.first);
e.second.second = lower_bound(vec.begin(), vec.end(), e.second.second) - vec.begin() + 1;
halfB.push_back(e.second.second);
}
for (int _ = 0; _ < 2; _++) {
sort(halfA.begin(), halfA.end());
halfA.resize(unique(halfA.begin(), halfA.end()) - halfA.begin());
swap(halfA, halfB);
}
MinCostFlow<int,int> solver(numNode);
int source = 0, sink = numNode - 1;
for (int node : halfA) solver.addEdge(source, node, 1, 0);
for (auto e : edges) solver.addEdge(e.second.first, e.second.second, 1, e.first);
for (int node : halfB) solver.addEdge(node, sink, 1, 0);
int totalCost, totalFlow;
tie(totalCost, totalFlow) = solver.getMCMF(source, sink, numDomino);
ans += totalCost;
cout << ans;
}
int main() {
Task();
Solve();
return 0;
}
