#include <bits/stdc++.h>
using namespace std;
int n, k;
int a[4040][4040], f[880][4040];
int Sum(int x, int y) {
  return a[y][y] + a[x - 1][x - 1] - a[x - 1][y] - a[y][x - 1];
}
void Solve(int f[], int g[], int l, int r, int opt_l, int opt_r) {
  if (l > r) return;
  int i, mid = l + r >> 1, pos = opt_l;
  g[mid] = 0x3f3f3f3f;
  for (i = opt_l; i <= min(opt_r, mid - 1); i++)
    if (f[i] + Sum(i + 1, mid) < g[mid])
      g[mid] = f[i] + Sum(i + 1, mid), pos = i;
  Solve(f, g, l, mid - 1, opt_l, pos);
  Solve(f, g, mid + 1, r, pos, opt_r);
}
namespace IStream {
char buffer[(1 << 16)], *S, *T;
char Get_Char() {
  if (S == T) {
    T = (S = buffer) + fread(buffer, 1, (1 << 16), stdin);
    if (S == T) return EOF;
  }
  return *S++;
}
int Get_Int() {
  char c = Get_Char();
  while (c < '0' || c > '9') c = Get_Char();
  return c - '0';
}
}  // namespace IStream
int main() {
  int i, j;
  cin >> n >> k;
  for (i = 1; i <= n; i++)
    for (j = 1; j <= n; j++) {
      a[i][j] =
          IStream::Get_Int() + a[i - 1][j] + a[i][j - 1] - a[i - 1][j - 1];
    }
  for (i = 1; i <= n; i++) f[1][i] = Sum(1, i);
  for (i = 2; i <= k; i++) Solve(f[i - 1], f[i], i, n, i - 1, n - 1);
  cout << f[k][n] / 2 << endl;
  return 0;
}
