#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
const int nax = 4010, kax = 810;
int n, K;
long long dp[kax][nax];
long long sum[nax][nax];
long long rsq(int l, int r) {
  return sum[r][r] + sum[l - 1][l - 1] - sum[r][l - 1] - sum[l - 1][r];
}
void compute(int k, int l, int r, int optl, int optr) {
  if (l > r) return;
  int mid = l + (r - l) / 2;
  pair<long long, int> best = {inf, optr};
  for (int j = max(mid, optl); j <= optr; ++j) {
    pair<long long, int> tmp = {dp[k - 1][j + 1] + rsq(mid, j), j};
    best = min(best, tmp);
  }
  int opt;
  tie(dp[k][mid], opt) = best;
  compute(k, l, mid - 1, optl, opt);
  compute(k, mid + 1, r, opt, optr);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  cin >> n >> K;
  for (int i = 1; i <= (int)n; ++i) {
    for (int j = 1; j <= (int)n; ++j) {
      char c;
      cin >> c;
      sum[i][j] = (c - '0');
    }
  }
  for (int i = 1; i <= (int)n; ++i) {
    for (int j = 1; j <= (int)n; ++j) {
      sum[i][j] += sum[i][j - 1];
    }
  }
  for (int j = 1; j <= (int)n; ++j) {
    for (int i = 1; i <= (int)n; ++i) {
      sum[i][j] += sum[i - 1][j];
    }
  }
  for (int j = 0; j < (int)K + 3; ++j) {
    for (int i = 0; i < (int)n + 3; ++i) {
      dp[j][i] = inf;
    }
  }
  dp[0][n + 1] = 0;
  for (int k = 1; k <= K; ++k) {
    compute(k, 1, n, 1, n);
  }
  cout << dp[K][1] / 2 << '\n';
}
