#include <bits/stdc++.h>
const int maxn = 4100, maxk = 800;
int dat[maxn][maxn], cost[maxn][maxn], dp[maxn][maxk];
int n, k;
char s[10000];
inline int getint() {
  char ch = getchar();
  int x = 0;
  while (ch < '0' || ch > '9') ch = getchar();
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x;
}
void work(int j, int l, int r, int dl, int dr) {
  int t = (l + r) >> 1, minw = 0x7fffffff, mink, mint;
  for (int i = dl; i <= dr; i++) {
    mint = dp[i][j - 1] + cost[i][t];
    if (mint < minw) {
      minw = mint;
      mink = i;
    }
  }
  dp[t][j] = minw;
  if (l < t) work(j, l, t - 1, dl, mink);
  if (t < r) work(j, t + 1, r, mink, dr);
}
int main() {
  n = getint();
  k = getint();
  for (int i = 1; i <= n; i++) {
    gets(s);
    for (int j = 1; j <= n; j++) {
      dat[i][j] = s[(j - 1) * 2] - '0' + dat[i][j - 1] + dat[i - 1][j] -
                  dat[i - 1][j - 1];
    }
  }
  for (int i = 0; i < n; i++)
    for (int j = i + 1; j <= n; j++)
      cost[i][j] = (dat[j][j] - dat[i][j] - dat[j][i] + dat[i][i]) / 2;
  for (int i = 0; i <= n; i++) dp[i][1] = cost[0][i];
  for (int i = 2; i <= k; i++) work(i, 1, n, 0, n - 1);
  printf("%d\n", dp[n][k]);
  return 0;
}
