#include <bits/stdc++.h>
using namespace std;
int mat[4002][4002], n, i, k, br, b;
int dp[802][4002];
int val(int i1, int b1, int i2, int b2) {
  return (mat[i2][b2] + mat[i1 - 1][b1 - 1] - mat[i1 - 1][b2] -
          mat[i2][b1 - 1]) /
         2;
}
int readInt() {
  bool minus = false;
  int result = 0;
  char ch;
  ch = getchar();
  while (true) {
    if (ch == '-') break;
    if (ch >= '0' && ch <= '9') break;
    ch = getchar();
  }
  if (ch == '-')
    minus = true;
  else
    result = ch - '0';
  while (true) {
    ch = getchar();
    if (ch < '0' || ch > '9') break;
    result = result * 10 + (ch - '0');
  }
  if (minus)
    return -result;
  else
    return result;
}
void rec(int le, int re, int lp, int rp) {
  if (le > re) return;
  int piv = lp, mid = (le + re) / 2;
  dp[i][mid] = 1e9;
  for (int g = lp; g <= min(rp, mid - 1); g++) {
    if (dp[i][mid] > val(g + 1, g + 1, mid, mid) + dp[i - 1][g]) {
      piv = g;
      dp[i][mid] = val(g + 1, g + 1, mid, mid) + dp[i - 1][g];
    }
  }
  rec(le, mid - 1, lp, piv);
  rec(mid + 1, re, piv, rp);
}
int main() {
  scanf("%d%d", &n, &k);
  for (i = 1; i <= n; i++)
    for (b = 1; b <= n; b++) mat[i][b] = readInt();
  for (i = 1; i <= n; i++) {
    br = 0;
    for (b = 1; b <= n; b++) {
      br += mat[i][b];
      mat[i][b] = br + mat[i - 1][b];
    }
  }
  for (i = 1; i <= n; i++) dp[0][i] = 1e9;
  for (i = 1; i <= k; i++) rec(1, n, i - 1, n - 1);
  printf("%d\n", dp[k][n]);
  return 0;
}
