#include <bits/stdc++.h>
using namespace std;
int n, k, a[4005][4005], f[4005][805];
template <typename T>
inline void Cin(T &x) {
  char c;
  T sign = 1;
  x = 0;
  for (c = getchar(); c < '0' || c > '9'; c = getchar())
    if (c == '-') sign = -1;
  for (; c >= '0' && c <= '9'; c = getchar()) x = x * 10 + c - '0';
  x *= sign;
}
void F(int g, int l, int r, int optl, int optr) {
  if (l > r) return;
  int mid = (l + r) / 2;
  f[mid][g] = (int)1e9;
  int optmid = -1;
  for (int i = optl; i <= optr; ++i) {
    int cost = f[i - 1][g - 1] +
               (a[mid][mid] + a[i - 1][i - 1] - a[i - 1][mid] - a[mid][i - 1]);
    if (f[mid][g] > cost) {
      f[mid][g] = cost;
      optmid = i;
    }
  }
  F(g, l, mid - 1, optl, optmid);
  F(g, mid + 1, r, optmid, optr);
}
int main() {
  Cin(n);
  Cin(k);
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      Cin(a[i][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[i][1] = a[i][i];
  for (int i = 2; i <= k; ++i) F(i, 1, n, 1, n);
  cout << f[n][k] / 2;
}
