#include <bits/stdc++.h>
#pragma GCC optimeze("ofast")
using namespace std;
int n, g, arr[4004][4004], ta[4004][4004], dp[4004][4004];
void read() {
  char x;
  cin >> n >> g;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cin >> x;
      arr[i][j] = x - '0';
      ta[i][j] = arr[i][j];
    }
  }
}
void build() {
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      if (i == 0 && j == 0) {
        continue;
      }
      if (j == 0) {
        ta[i][j] += ta[i - 1][j];
      }
      if (i == 0) {
        ta[i][j] += ta[i][j - 1];
      }
      if (i > 0 && j > 0) {
        ta[i][j] += ta[i - 1][j] + ta[i][j - 1] - ta[i - 1][j - 1];
      }
    }
  }
}
int C(int i, int j) {
  return (ta[j][j] + ta[i - 1][i - 1] - ta[i - 1][j] - ta[j][i - 1]) >> 1;
}
void compute(int i, int l, int r, int opl, int opr) {
  if (l > r) return;
  int mid = (l + r) >> 1;
  dp[i][mid] = 1e9 + 7;
  int best = -1;
  for (int k = opl; k <= min(opr, mid - 1); k++) {
    int est = dp[i - 1][k] + C(k + 1, mid);
    if (dp[i][mid] > est) {
      dp[i][mid] = est;
      best = k;
    }
  }
  compute(i, l, mid - 1, opl, best);
  compute(i, mid + 1, r, best, opr);
}
void callcdp() {
  for (int i = 0; i < n; i++) {
    dp[1][i] = C(0, i);
  }
  for (int i = 2; i <= g; i++) {
    compute(i, 0, n - 1, 0, n - 1);
  }
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  read();
  build();
  callcdp();
  cout << dp[g][n - 1];
  return 0;
}
