#include <bits/stdc++.h>
const double Pi = acos(-1.0);
using namespace std;
const int inf = 1 << 29;
int N, K;
int u[4005][4005];
int dp[2][4005];
void calc(int i, int l, int r, int kl, int kr) {
  if (l > r) return;
  int mid = (l + r) >> 1, best;
  dp[i][mid] = inf;
  for (int k = kl; k <= min(mid, kr); k++) {
    int cost =
        (u[mid][mid] - u[mid][k - 1] - u[k - 1][mid] + u[k - 1][k - 1]) >> 1;
    if (dp[i][mid] > dp[1 - i][k - 1] + cost) {
      dp[i][mid] = dp[1 - i][k - 1] + cost;
      best = k;
    }
  }
  calc(i, l, mid - 1, kl, best);
  calc(i, mid + 1, r, best, kr);
}
int main(int argc, char** argv) {
  scanf("%d %d", &N, &K);
  for (int i = 1; i <= N; i++) {
    for (int j = 1; j <= N; j++) {
      getchar();
      u[i][j] = (getchar() - '0') + u[i - 1][j] + u[i][j - 1] - u[i - 1][j - 1];
    }
    dp[1][i] = u[i][i] >> 1;
  }
  for (int i = 2; i <= K; i++) calc(i & 1, 1, N, 1, N);
  printf("%d\n", dp[K & 1][N]);
  return 0;
}
