#include <bits/stdc++.h>
using namespace std;
const int OO = 1e9;
const long long INF = 1e18;
const int irand(int lo, int hi) {
  return ((double)rand() / (RAND_MAX + 1.0)) * (hi - lo + 1) + lo;
}
const long long lrand(long long lo, long long hi) {
  return ((double)rand() / (RAND_MAX + 1.0)) * (hi - lo + 1) + lo;
}
template <typename T>
T getnum() {
  int sign = 1;
  T ret = 0;
  char c;
  do {
    c = getchar();
  } while (c == ' ' || c == '\n');
  if (c == '-')
    sign = -1;
  else
    ret = c - '0';
  while (1) {
    c = getchar();
    if (c < '0' || c > '9') break;
    ret = 10 * ret + c - '0';
  }
  return sign * ret;
}
inline void ini(int& x) { x = getnum<int>(); }
inline void scani(int& x) { scanf("%d", &x); }
const int N = 4005;
const int K = 805;
int n, k;
int hate[N][N];
int hatep[N][N];
inline void pre() {
  for (int i = 1; i <= n; i += 1) {
    for (int j = 2; j <= n; j += 1) hate[i][j] += hate[i][j - 1];
  }
  for (int j = 1; j <= n; j += 1) {
    for (int i = 2; i <= n; i += 1) hate[i][j] += hate[i - 1][j];
  }
  for (int i = 1; i <= n; i += 1) {
    for (int j = i; j <= n; j += 1) {
      hatep[i][j] =
          hate[j][j] - hate[i - 1][j] - hate[j][i - 1] + hate[i - 1][i - 1];
    }
  }
}
int dp[K][N];
void dpdnc(int level, int l, int r, int bl, int br) {
  if (l > r) return;
  int m = (l + r) / 2;
  int best = OO;
  int bm = -1;
  for (int i = bl; i <= min(m, br); i += 1) {
    int tmp = dp[level - 1][i - 1] + hatep[i][m];
    if (tmp < best) {
      best = tmp;
      bm = i;
    }
  }
  dp[level][m] = best;
  dpdnc(level, l, m - 1, bl, bm);
  dpdnc(level, m + 1, r, bm, br);
}
int main() {
  n = getnum<int>();
  k = getnum<int>();
  for (int i = 1; i <= n; i += 1) {
    for (int j = 1; j <= n; j += 1) {
      hate[i][j] = getnum<int>();
    }
  }
  pre();
  for (int j = 1; j <= n; j += 1) dp[1][j] = hatep[1][j];
  for (int i = 2; i <= k; i += 1) {
    dpdnc(i, 1, n, 1, n);
  }
  printf("%d\n", dp[k][n] / 2);
  return 0;
}
