#include <bits/stdc++.h>
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("sse2")
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template <class T>
T& get(T& n) {
  int p;
  bool f;
  f = false;
  n = 0;
  do {
    p = getchar();
  } while (!isdigit(p) && p != '-');
  if (p == '-') {
    f = true;
    p = getchar();
  }
  while (isdigit(p)) {
    n = (n << 3) + (n << 1) + (p - '0');
    p = getchar();
  }
  n = (f ? -n : n);
  return n;
}
int n, i, j, k, l, sum = 0, flag = 0, t, a[4001][4001], ans = 0;
vector<int> dp_before(4001), dp_cur(4001, 1000000007);
int C(int i, int j) {
  return a[j][j] - a[i - 1][j] - a[j][i - 1] + a[i - 1][i - 1];
}
void compute(int l, int r, int optl, int optr) {
  if (l > r) return;
  int mid = (l + r) >> 1;
  pair<long long, int> best = {1000000007, -1};
  for (int k = optl; k <= min(mid, optr); k++) {
    best = min(best, {dp_before[k - 1] + C(k, mid), k});
  }
  dp_cur[mid] = best.first;
  int opt = best.second;
  compute(l, mid - 1, optl, opt);
  compute(mid + 1, r, opt, optr);
}
void solve() {
  get(n);
  get(k);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      get(a[i][j]);
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      a[i][j] += a[i][j - 1] + a[i - 1][j] - a[i - 1][j - 1];
    }
  }
  dp_cur[0] = 0;
  for (int i = 1; i <= k; i++) {
    dp_before = dp_cur;
    compute(1, n, 1, n);
  }
  cout << dp_cur[n] / 2 << '\n';
}
signed main() {
  int test = 1;
  while (test--) {
    solve();
  }
  return 0;
}
