#include <bits/stdc++.h>
using namespace std;
int u[4001][4001], c[4001][4001], dp[801][4001];
int n, k;
void compute(int i, int l, int r, int opl, int opr) {
  int m = (l + r) >> 1, bestz = -1, fin = min(m - 1, opr), t;
  for (int z = opl; z <= fin; z++) {
    t = dp[i - 1][z] + c[z + 1][m];
    if (t < dp[i][m]) dp[i][m] = t, bestz = z;
  }
  if (bestz != -1) {
    if (l <= m - 1) compute(i, l, m - 1, opl, bestz);
    if (m + 1 <= r) compute(i, m + 1, r, bestz, opr);
  }
}
int main() {
  scanf("%d%d\n", &n, &k);
  char buffer[10000];
  for (int i = 1; i <= n; i++) {
    gets(buffer);
    for (int j = 1; j <= n; j++) {
      u[i][j] = buffer[2 * (j - 1)] - '0';
      u[i][j] += u[i][j - 1];
    }
  }
  for (int i = 1; i <= n; i++)
    for (int j = i + 1; j <= n; j++)
      c[i][j] = c[i][j - 1] + u[j][j] - u[j][i - 1];
  for (int i = 1; i <= k; i++)
    for (int j = 0; j <= n; j++) dp[i][j] = 1 << 29;
  dp[0][0] = 0;
  for (int i = 1; i <= n; i++) dp[1][i] = c[1][i];
  for (int i = 2; i <= k; i++) compute(i, i, n, i - 1, n);
  printf("%d", dp[k][n]);
  return 0;
}
