#include <bits/stdc++.h>
using namespace std;
const int MAXN = 4000 + 5;
const int MAXK = 800 + 3;
int g[MAXN][MAXN];
int tp[MAXN][MAXN];
int cs[MAXN][MAXN];
int dp[2][MAXN];
void vez(int l, int r, int p1, int p2) {
  if (l >= r) return;
  int mid = (l + r) / 2;
  int& ans = dp[1][mid];
  ans = MAXN * MAXN;
  int pr = mid;
  for (int i = p1; i <= p2 && i < mid; i++) {
    if (ans > dp[0][i] + cs[i + 1][mid]) {
      ans = dp[0][i] + cs[i + 1][mid];
      pr = i;
    }
  }
  vez(l, mid, p1, pr);
  vez(mid + 1, r, pr, p2);
}
int main() {
  ios::sync_with_stdio(false);
  int n, k;
  scanf("%d%d", &n, &k);
  for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++) g[i][j] = (getchar(), getchar()) - '0';
  for (int i = 0; i < n; i++) {
    int s = 0;
    for (int j = i - 1; j >= 0; j--) {
      s += g[i][j];
      tp[j][i] = s;
    }
  }
  for (int i = 0; i < n; i++) {
    int s = 0;
    for (int j = i + 1; j < n; j++) {
      s += tp[i][j];
      cs[i][j] = s;
      if (!i) dp[0][j] = s;
    }
  }
  for (int kk = 1; kk < k; kk++) {
    vez(0, n, 0, n - 1);
    for (int i = 0; i < n; i++) dp[0][i] = dp[1][i];
  }
  cout << dp[0][n - 1] << endl;
  return 0;
}
