#include <bits/stdc++.h>
using namespace std;
int mat[4005][4005];
int acum[4005][4005];
int dp[4005][805];
int step(int n, int k, int min_i, int max_i) {
  dp[n][k] = dp[min_i - 1][k - 1] + (acum[n][n] + acum[min_i - 1][min_i - 1] -
                                     acum[n][min_i - 1] - acum[min_i - 1][n]) /
                                        2;
  for (int i = min_i + 1; i <= max_i; i++) {
    if (dp[i - 1][k - 1] + (acum[n][n] + acum[i - 1][i - 1] - acum[n][i - 1] -
                            acum[i - 1][n]) /
                               2 <
        dp[n][k]) {
      dp[n][k] = dp[i - 1][k - 1] + (acum[n][n] + acum[i - 1][i - 1] -
                                     acum[n][i - 1] - acum[i - 1][n]) /
                                        2;
      min_i = i;
    }
  }
  return min_i;
}
void conquer(int min_n, int max_n, int k, int min_i, int max_i) {
  if (min_n > max_n) return;
  max_i = min(max_n, max_i);
  if (min_n == max_n) {
    step(min_n, k, min_i, max_i);
    return;
  }
  if (min_i == max_i) {
    for (int i = min_n; i <= max_n; i++) step(i, k, min_i, max_i);
    return;
  }
  int mid = (min_n + max_n) / 2;
  int i = step(mid, k, min_i, min(max_i, mid));
  conquer(min_n, mid - 1, k, min_i, i);
  conquer(mid + 1, max_n, k, i, max_i);
}
char buff[100005];
int main() {
  int n, k;
  scanf("%d %d\n", &n, &k);
  for (int i = 1; i <= n; i++) {
    int acum2 = 0;
    gets(buff);
    for (int j = 1; j <= n; j++) {
      acum2 += buff[j * 2 - 2] - '0';
      acum[i][j] = acum[i - 1][j] + acum2;
    }
  }
  for (int i = 1; i <= n; i++) {
    dp[i][1] = acum[i][i] / 2;
  }
  for (int j = 2; j <= k; j++) {
    conquer(1, n, j, j - 1, n);
  }
  printf("%d\n", dp[n][k]);
  return 0;
}
