#include <bits/stdc++.h>
using namespace std;
const int N = 4005, K = 805, oo = 1e9;
int dp[K][N], n, a[N][N], k, s[N][N];
int cost(int l, int r) {
  return (s[r][r] - s[l - 1][r] - s[r][l - 1] + s[l - 1][l - 1]);
}
void read(int& n) {
  n = 0;
  while (true) {
    char c = getchar();
    if (c == '\r') {
      c = getchar();
      break;
    }
    if (c == ' ' || c == '\n' || c == EOF) {
      break;
    }
    n = (n << 1) + (n << 3) + c - '0';
  }
}
void write(int n) {
  if (n > 9) {
    write(n / 10);
    putchar(n % 10 + '0');
  } else {
    putchar(n + '0');
  }
}
void calc(int L, int R, int i, int j, int k) {
  if (L > R) return;
  int mid = (L + R) >> 1;
  int id = -1;
  for (int p = i; p <= j; ++p)
    if (p < mid) {
      if (dp[k][mid] >= dp[k - 1][p] + cost(p + 1, mid)) {
        id = p;
        dp[k][mid] = dp[k - 1][p] + cost(p + 1, mid);
      }
    }
  calc(L, mid - 1, i, id, k);
  calc(mid + 1, R, id, j, k);
}
int main(int argc, char const* argv[]) {
  read(n);
  read(k);
  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) {
      s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];
    }
  }
  for (int i = 0; i <= n; ++i) {
    for (int j = 0; j <= k; ++j) dp[j][i] = oo;
  }
  dp[0][0] = 0;
  for (int i = 1; i <= k; ++i) calc(1, n, 0, n, i);
  write(dp[k][n] / 2);
  return 0;
}
