#include <bits/stdc++.h>
using namespace std;
const int MAXN = 4040;
const int MAXK = 810;
int n, k;
int f[MAXK][MAXN];
int a[MAXN][MAXN];
int cost(int i, int j) { return (a[j][j] - 2 * a[i][j] + a[i][i]) >> 1; }
void compute(int k, int l, int r, int optl, int optr) {
  if (l > r) return;
  int m = (l + r) / 2;
  pair<int, int> best = {1e9, -1};
  for (int i = optl; i <= min(m, optr); i++)
    best = min(best, {f[k - 1][i] + cost(i, m), i});
  f[k][m] = best.first;
  int opt = best.second;
  compute(k, l, m - 1, optl, opt);
  compute(k, m + 1, r, opt, optr);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie();
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) scanf("%d", &a[i][j]);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
      a[i][j] += a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
  for (int i = 1; i <= n; i++) f[1][i] = cost(0, i);
  for (int i = 2; i <= k; i++) compute(i, 1, n, 1, n);
  printf("%d", f[k][n]);
  return 0;
}
