#include <bits/stdc++.h>
using namespace std;
inline int read(void) {
  int x = 0, f = 1;
  char ch = getchar();
  while (ch < '0' || ch > '9') {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (ch >= '0' && ch <= '9') {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return f * x;
}
const int maxn = 4005, maxK = 805;
int n, K;
int pl, pr;
int cost[maxn][maxn];
int sum[maxn][maxn];
int f[maxK][maxn];
int now;
void update(int& x, int val, int y, int& mn) {
  if (val < x) x = val, mn = y;
}
void solve(int l, int r, int L, int R, int id) {
  if (L > R) return;
  int mid = (L + R) >> 1;
  while (pr < mid) ++pr, now += sum[pr][pr] - sum[pr][pl - 1];
  while (pr > mid) now -= sum[pr][pr] - sum[pr][pl - 1], --pr;
  while (pl > l) --pl, now += sum[pl][pr] - sum[pl][pl - 1];
  while (pl < l) now -= sum[pl][pr] - sum[pl][pl - 1], ++pl;
  int mn = 0;
  update(f[id][mid], f[id - 1][pl - 1] + now, pl, mn);
  while (pl < min(mid, r)) {
    now -= sum[pl][pr] - sum[pl][pl - 1], ++pl;
    update(f[id][mid], f[id - 1][pl - 1] + now, pl, mn);
  }
  solve(l, mn, L, mid - 1, id);
  solve(mn, r, mid + 1, R, id);
}
int main() {
  n = read();
  K = read();
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
      cost[i][j] = read(), sum[i][j] = sum[i][j - 1] + cost[i][j];
  memset(f, 0x3f, sizeof f);
  f[0][0] = 0;
  pl = 1;
  pr = 0;
  for (int i = 1; i <= K; ++i) {
    f[i][0] = 0;
    solve(1, n, 1, n, i);
  }
  printf("%d\n", f[K][n]);
  return 0;
}
