#include <bits/stdc++.h>
using namespace std;
constexpr int MAXN = 4000;
constexpr int MAXK = 800;
int N, K, Up[MAXN][MAXN], rgu[MAXN][MAXN], dp[MAXN][MAXK + 1];
void sv(int k, int ns, int ne, int ps, int pe) {
  if (ns > ne) return;
  int n = (ns + ne) / 2;
  int& ans = dp[n][k];
  ans = INT_MAX;
  int optP = -1;
  for (int p = ps; p <= min(n, pe); p++) {
    if (k == 1 && p != 0) continue;
    int ta = 0;
    if (p > 0 && k > 1) ta += dp[p - 1][k - 1];
    ta += rgu[p][n];
    if (ta < ans) {
      ans = ta;
      optP = p;
    }
  }
  sv(k, ns, n - 1, ps, optP);
  sv(k, n + 1, ne, optP, pe);
}
int main() {
  scanf("%d%d", &N, &K);
  char s[10000];
  gets(s);
  for (int n = 0; n < int(N); n++) {
    gets(s);
    for (int m = 0; m < int(N); m++) {
      int& x = Up[n][m];
      x = s[m * 2] - '0';
      if (m > 0) x += Up[n][m - 1];
    }
  }
  for (int n = 0; n < int(N); n++)
    for (int m = n; m < int(N); m++) {
      int& x = rgu[n][m];
      x = Up[m][m] - (n > 0 ? Up[m][n - 1] : 0);
      if (m > n) x += rgu[n][m - 1];
    }
  for (int k = 1; k < int(K + 1); k++) sv(k, 0, N - 1, 0, N - 1);
  printf("%d\n", dp[N - 1][K]);
}
