#include <bits/stdc++.h>
using namespace std;
#define FNAME "test"
#define int long long
const int N = 2005;
int n, k;
int grid[N][N];
int sum = 0;
vector<vector<vector<int>>> dp, mx, pmx, t;
void Task() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
cout << fixed << setprecision(9);
if (fopen(FNAME".inp","r")) {
freopen(FNAME".inp","r",stdin);
freopen(FNAME".out","w",stdout);
}
}
void Solve() {
//Your Code
cin >> n >> k;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> grid[i][j];
sum += grid[i][j];
}
}
dp.resize(2, vector<vector<int>>(n + 1, vector<int>(n + 1, 0)));
mx.resize(2, vector<vector<int>>(n + 1, vector<int>(n + 1, 0)));
pmx.resize(2, vector<vector<int>>(n + 1, vector<int>(n + 1, 0)));
t.resize(2, vector<vector<int>>(n + 1, vector<int>(n + 1, 0)));
for (int dom = 1; dom <= k; dom++) {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (i == 1 && j == 1) continue;
// (i - 1, j) -> (i, j)
dp[0][i][j] = max(pmx[0][n][j - 1], pmx[1][n][j - 1]);
if (i - 2 >= 0) dp[0][i][j] = max(pmx[0][i - 2][n], pmx[1][i - 2][n]);
dp[0][i][j] += grid[i - 1][j] + grid[i][j];
mx[0][i][j] = max(dp[0][i][j], max(mx[0][i - 1][j], mx[0][i][j - 1]));
// (i, j - 1) -> (i, j)
dp[1][i][j] = max(pmx[0][i - 1][n], pmx[1][i - 1][n]);
if (j - 2 >= 0) dp[1][i][j] = max(pmx[0][n][j - 2], pmx[1][n][j - 2]);
dp[1][i][j] += grid[i][j - 1] + grid[i][j];
mx[1][i][j] = max(dp[1][i][j], max(mx[1][i - 1][j], mx[1][i][j - 1]));
}
}
pmx = mx;
mx = t;
}
int res = sum - max(pmx[0][n][n], pmx[1][n][n]);
cout << res << '\n';
}
signed main() {
Task();
Solve();
cerr << "\nTime run: " << 1000*clock()/CLOCKS_PER_SEC << "ms";
return 37^37;
}
