#include <bits/stdc++.h>
using namespace std;
int gn() {
  int c;
  while ((c = getchar()) == ' ' || c == '\n')
    ;
  return c - '0';
}
int u[4010][4010], su[4010][4010], w[4010][4010], s[810][4010], dp[810][4010];
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) u[i][j] = gn();
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) su[i][j] = su[i][j - 1] + u[i][j];
  for (int i = 1; i <= n; i++)
    for (int j = i + 1; j <= n; j++)
      w[i][j] = w[i][j - 1] + su[j][j] - su[j][i - 1];
  for (int i = 1; i <= n; i++) {
    dp[1][i] = w[1][i];
    s[1][i] = 0;
  }
  for (int i = 2; i <= m; i++) {
    s[i][n + 1] = n;
    for (int j = n; j > i; j--) {
      dp[i][j] = 514514514;
      for (int k = s[i - 1][j]; k <= s[i][j + 1]; k++) {
        int now = dp[i - 1][k] + w[k + 1][j];
        if (now < dp[i][j]) {
          dp[i][j] = now;
          s[i][j] = k;
        }
      }
    }
  }
  printf("%d\n", dp[m][n]);
  return 0;
}
