#include <bits/stdc++.h>
using namespace std;
void scanint(int &x) {
  register int c = getchar();
  x = 0;
  for (; (c < 48 || c > 57); c = getchar())
    ;
  for (; c > 47 && c < 58; c = getchar()) {
    x = (x << 1) + (x << 3) + c - 48;
  }
}
int n, k_, dp[1010][4040], mat[4040][4040];
void preprocess() {
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= i; j++) mat[i][j] = 0;
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      mat[i][j] += mat[i - 1][j] + mat[i][j - 1] - mat[i - 1][j - 1];
    }
  }
}
int cost(int i, int j) {
  int x = mat[j][j] - mat[i - 1][j] - mat[j][i - 1] + mat[i - 1][i - 1];
  return x;
}
void func(int k, int l, int r, int optL, int optR) {
  if (r < l) return;
  int mid = (l + r) / 2;
  int opt = -1;
  int best = 1010101010LL;
  for (int i = optL; i <= min(mid - 1, optR); i++) {
    int x = dp[k - 1][i] + cost(i + 1, mid);
    if (x < best) {
      opt = i;
      best = x;
    }
  }
  dp[k][mid] = (best == 1010101010LL) ? 0 : best;
  func(k, l, mid - 1, optL, opt);
  func(k, mid + 1, r, max(opt, 1), optR);
}
int main() {
  scanint(n);
  scanint(k_);
  memset(mat, 0, sizeof mat);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      scanint(mat[i][j]);
    }
  }
  preprocess();
  memset(dp, 0, sizeof dp);
  for (int i = 1; i <= n; i++) {
    dp[1][i] = cost(1, i);
  }
  for (int k = 2; k <= k_; k++) {
    func(k, 1, n, 1, n);
  }
  printf("%d\n", dp[k_][n]);
  return 0;
}
