#include <bits/stdc++.h>
using namespace std;
const int MAXN = 4002;
const int MAXK = 802;
const int INF = 2e9;
int pref[MAXN][MAXN];
int dp[MAXN][MAXK];
int opt[MAXN][MAXK];
int u[MAXN][MAXN], n, k;
void solve(int d, int l, int r, int optl, int optr) {
  if (l > r) return;
  if (l == r) {
    for (int i = optl; i <= optr && i < l; ++i) {
      dp[l][d] = min(dp[l][d], dp[i][d - 1] + pref[l][l] - pref[l][i] -
                                   pref[i][l] + pref[i][i]);
    }
    return;
  }
  int mid = (l + r) / 2;
  for (int i = optl; i <= optr && i < mid; ++i) {
    if (dp[i][d - 1] + pref[mid][mid] - pref[mid][i] - pref[i][mid] +
            pref[i][i] <
        dp[mid][d]) {
      opt[mid][d] = i;
      dp[mid][d] = dp[i][d - 1] + pref[mid][mid] - pref[mid][i] - pref[i][mid] +
                   pref[i][i];
    }
  }
  solve(d, l, mid - 1, optl, opt[mid][d]);
  solve(d, mid + 1, r, opt[mid][d], optr);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> n >> k;
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      char c;
      cin >> c;
      u[i][j] = c - '0';
      pref[i][j] =
          pref[i][j - 1] + pref[i - 1][j] - pref[i - 1][j - 1] + u[i][j];
    }
  }
  for (int i = 1; i <= n; ++i) {
    dp[i][1] = pref[i][i];
  }
  for (int i = 2; i <= k; ++i) {
    for (int j = 1; j <= n; ++j) {
      dp[j][i] = INF;
    }
    solve(i, 1, n, 1, n);
  }
  cout << dp[n][k] / 2 << "\n";
  return 0;
}
