#include <bits/stdc++.h>
using namespace std;
const int K = 805;
const int N = 4005;
const int INF = 1e9 + 5;
int n, k, a[N][N];
int cost[N][N], f[K][N];
void compute(int at, int l, int r, int opt_l, int opt_r) {
  if (l > r) return;
  int mid = l + r >> 1, opt = -1;
  int lo = opt_l, hi = opt_r;
  while (hi - lo > 50) {
    int one = lo + (hi - lo) / 3;
    int two = hi - (hi - lo) / 3;
    if (f[at - 1][one] + cost[one + 1][mid] <=
        f[at - 1][two] + cost[two + 1][mid]) {
      hi = two - 1;
    } else {
      lo = one + 1;
    }
  }
  f[at][mid] = INF;
  for (int i = lo; i <= hi; ++i) {
    if (f[at][mid] > f[at - 1][i] + cost[i + 1][mid]) {
      f[at][mid] = f[at - 1][i] + cost[i + 1][mid];
      opt = i;
    }
  }
  if (opt == -1) return;
  compute(at, l, mid - 1, opt_l, opt);
  compute(at, mid + 1, r, opt, opt_r);
}
inline void fastInt(int *a) {
  register char c = 0;
  while (c < 33) c = getchar();
  *a = 0;
  while (c > 33) {
    *a = *a * 10 + c - '0';
    c = getchar();
  }
}
int main() {
  fastInt(&n);
  fastInt(&k);
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      fastInt(&a[i][j]);
      a[i][j] += a[i][j - 1];
    }
  }
  for (int i = 1; i <= n; ++i) {
    cost[i][i] = 0;
    for (int j = i + 1; j <= n; ++j) {
      cost[i][j] = cost[i][j - 1] + a[j][j - 1] - a[j][i - 1];
      cost[j][i] = INF;
    }
  }
  for (int i = 1; i <= n; ++i) {
    f[1][i] = cost[1][i];
  }
  for (int i = 2; i <= k; ++i) {
    compute(i, i, n, 0, n);
  }
  printf("%d\n", f[k][n]);
  return 0;
}
