#include <bits/stdc++.h>
using namespace std;
const int sz = 4005;
char s[sz << 1];
int a[sz][sz], dp[sz][sz];
void dnc(int i, int jl, int jr, int kl, int kr) {
  if (jl > jr) return;
  int jm = jl + jr + 1 >> 1, km;
  int &w = dp[i][jm] = a[i][i];
  for (int r = kl; r < kr && jm > 1; r++) {
    int v = dp[r][jm - 1] + a[i][i] - a[r][i];
    if (v < w) w = v, km = r;
  }
  dnc(i, jl, jm - 1, kl, km + 1);
  dnc(i, jm + 1, jr, km, kr);
}
int main() {
  int n, k;
  cin >> n >> k;
  gets(s);
  for (int i = 1; i <= n; i++) {
    gets(s);
    for (int j = 1; j <= n; j++) {
      a[i][j] = s[(j - 1) << 1] - '0';
      if (i > j) a[i][j] = 0;
      a[i][j] += a[i][j - 1] + a[i - 1][j] - a[i - 1][j - 1];
    }
  }
  for (int i = 1; i <= n; i++) {
    dnc(i, 1, min(i, k), 1, i);
    for (int j = i + 1; j <= k; j++) dp[i][j] = dp[i][j - 1];
  }
  cout << dp[n][k];
}
