#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
const int MAXN = 4000;
const int MAXK = 800;
int f[MAXK + 10][MAXN + 10], s[MAXN + 10][MAXN + 10], w[MAXN + 10][MAXN + 10],
    a[MAXN + 10][MAXN + 10];
void Read(int &x) {
  char ch;
  int flg = 1;
  while (ch = getchar(), ch < '0' || ch > '9')
    if (ch == '-') flg = -flg;
  x = ch - '0';
  while (ch = getchar(), ch >= '0' && ch <= '9') x = x * 10 + ch - '0';
  x *= flg;
}
int main() {
  int n, m;
  scanf("%d%d", &n, &m);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) Read(a[i][j]);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
      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++)
    for (int j = i; j <= n; j++)
      w[i][j] = a[j][j] + a[i - 1][i - 1] - a[i - 1][j] - a[j][i - 1];
  for (int i = 1; i <= n; i++) f[1][i] = w[1][i];
  for (int i = 2; i <= m; i++) {
    s[i][n + 1] = n;
    for (int j = n; j >= 1; j--) {
      f[i][j] = INF;
      for (int k = s[i - 1][j]; k <= s[i][j + 1] && k < j; k++) {
        if (f[i][j] > f[i - 1][k] + w[k + 1][j]) {
          f[i][j] = f[i - 1][k] + w[k + 1][j];
          s[i][j] = k;
        }
      }
    }
  }
  printf("%d\n", f[m][n] / 2);
  return 0;
}
