#include <bits/stdc++.h>
using namespace std;
const int MAXN = 4010;
const int INF = 1000000000;
int a[MAXN][MAXN], sum[MAXN][MAXN], dp[MAXN][MAXN], par[MAXN][MAXN];
int read() {
  char c = getchar();
  while (c < '0' || c > '9') c = getchar();
  return c - '0';
}
int main() {
  int n, k;
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) {
    int x = 0;
    for (int j = 1; j <= n; j++) {
      x += read();
      sum[i][j] = sum[i - 1][j] + x;
    }
  }
  for (int i = 1; i <= n; i++) dp[i][0] = INF;
  for (int i = 1; i <= n; i++) {
    par[i][k + 1] = i - 1;
    for (int j = k; j >= 1; j--) {
      dp[i][j] = INF;
      for (int x = par[i - 1][j]; x <= par[i][j + 1]; x++) {
        int val = dp[x][j - 1] + sum[i][i] - sum[i][x] - sum[x][i] + sum[x][x];
        if (val < dp[i][j]) {
          par[i][j] = x;
          dp[i][j] = val;
        }
      }
    }
  }
  printf("%d\n", dp[n][k] / 2);
  return 0;
}
