#include <bits/stdc++.h>
using namespace std;
int N, K;
int C[4005][4005], dp[805][4005];
int C1[4005][4005];
void prep() {
  scanf("%d %d", &N, &K);
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= N; j++) {
      getchar();
      C[i][j] = getchar() - '0';
      C[i][j] += C[i - 1][j] + C[i][j - 1] - C[i - 1][j - 1];
    }
    dp[1][i] = C[i][i];
  }
  for (int i = 0; i < N; i++) {
    for (int j = i + 1; j <= N; j++) {
      C1[i][j] = C[j][j] - C[i][j] - C[j][i] + C[i][i];
    }
  }
}
void dnc(int now, int l, int r, int kl, int kr) {
  if (l > r) return;
  int mid = (l + r) >> 1;
  int bestid = -1, best = 1000000000;
  int atp;
  for (int k = kl; k <= kr && k <= mid; k++) {
    atp = dp[now - 1][k - 1] + C1[k - 1][mid];
    if (best > atp) {
      best = atp;
      bestid = k;
    }
  }
  dp[now][mid] = best;
  dnc(now, l, mid - 1, kl, bestid);
  dnc(now, mid + 1, r, bestid, kr);
}
int main() {
  prep();
  for (int i = 2; i <= K; i++) {
    dnc(i, i, N, i, N);
  }
  printf("%d\n", dp[K][N] >> 1);
}
