#include <bits/stdc++.h>
using namespace std;
int n, k;
int mat[4110][4110];
int memo[4110][880];
int opt[4110][880];
inline int custo(int x, int y) {
  return (mat[y][y] - mat[y][x - 1] - mat[x - 1][y] + mat[x - 1][x - 1]) / 2;
}
inline void sc(int& x) {
  register int c = getchar();
  x = 0;
  for (; (c < 48 || c > 57); c = getchar())
    ;
  for (; c > 47 && c < 58; c = getchar()) {
    x = (x << 1) + (x << 3) + c - 48;
  }
}
void solve(int g, int l, int r, int lo, int ro) {
  if (l > r) return;
  int pos = ro;
  int mid = (l + r) >> 1;
  memo[mid][g] = 0x3f3f3f3f;
  for (int y = ro; y >= max(lo, mid); y--) {
    if (custo(mid, y) + memo[y + 1][g - 1] < memo[mid][g]) {
      pos = y;
      memo[mid][g] = custo(mid, y) + memo[y + 1][g - 1];
    }
  }
  solve(g, l, mid - 1, lo, pos);
  solve(g, mid + 1, r, pos, ro);
  return;
}
int main() {
  scanf("%d %d", &n, &k);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) sc(mat[i][j]);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
      mat[i][j] += mat[i - 1][j] + mat[i][j - 1] - mat[i - 1][j - 1];
  memo[n + 1][0] = 0;
  for (int i = 0; i <= n; i++) memo[i][0] = 0x3f3f3f3f;
  for (int i = 1; i <= k; i++) solve(i, 1, n, 1, n);
  printf("%d\n", memo[1][k]);
  return 0;
}
