#include <bits/stdc++.h>
using namespace std;
int n, K, ar[4002][4002];
long long pre[4002][4002], dp[4002][802];
int k;
long long CostFunc(int x, int y) {
  return (pre[y][y] - pre[y][x - 1] - pre[x - 1][y] + pre[x - 1][x - 1]);
}
long long go(int l, int r, int x, int y) {
  if (l > r) return 0;
  int md = (l + r) / 2;
  long long &ret = dp[md][k];
  if (ret != -1) return ret;
  ret = 10000000005;
  int idx;
  for (int i = x; i <= min(y, md); i++) {
    long long tmp = dp[i][k - 1] + CostFunc(i + 1, md);
    if (ret > tmp) {
      ret = tmp;
      idx = i;
    }
  }
  go(l, md - 1, x, idx);
  go(md + 1, r, idx, y);
}
int main() {
  int i, j;
  cin >> n >> K;
  getchar();
  for (i = 1; i <= n; i++) {
    for (j = 1; j <= n; j++) {
      char ch = getchar();
      getchar();
      ar[i][j] = ch - '0';
      pre[i][j] =
          pre[i][j - 1] + pre[i - 1][j] - pre[i - 1][j - 1] + (ar[i][j]);
    }
  }
  memset(dp, -1, sizeof(dp));
  for (i = 1; i <= n; i++) {
    dp[i][1] = CostFunc(1, i);
  }
  for (k = 2; k <= K; k++) {
    go(1, n, 1, n);
  }
  long long ans = dp[n][K];
  cout << ((ans) >> 1) << "\n";
  return 0;
}
