#include <bits/stdc++.h>
using namespace std;
int pref[4001][4001];
int dp[801][4001];
inline int read_int() {
  int s = 1, x = 0, c = getchar();
  while (c <= 32) c = getchar();
  if (c == '-') {
    s = -1;
    c = getchar();
  }
  while ('0' <= c && c <= '9') {
    x = x * 10 + c - '0';
    c = getchar();
  }
  return x * s;
}
inline void print_int(int x) {
  if (x < 0) putchar('-'), x = -x;
  char s[20];
  int n = 0;
  while (x || !n) {
    s[n++] = '0' + x % 10;
    x /= 10;
  }
  for (int i = n - 1; i >= 0; i--) putchar(s[i]);
  putchar('\n');
}
inline int cnt(int l, int r) {
  return (pref[r + 1][r + 1] - pref[r + 1][l] - pref[l][r + 1] + pref[l][l]) >>
         1;
}
void f(int i, int l, int r, int optl, int optr) {
  int m = (l + r) >> 1;
  int opt = -1;
  for (int j = optl; j <= min(optr, m); j++) {
    if (dp[i - 1][j - 1] + cnt(j, m) < dp[i][m]) {
      dp[i][m] = dp[i - 1][j - 1] + cnt(j, m);
      opt = j;
    }
  }
  if (l + 1 == r) {
    return;
  }
  if (opt >= 0) {
    f(i, l, m, optl, opt);
    f(i, m, r, opt, optr);
  } else {
    f(i, m, r, optl, optr);
  }
}
signed main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  int n, k;
  n = read_int();
  k = read_int();
  int x;
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      x = read_int();
      pref[i + 1][j + 1] = pref[i + 1][j] + pref[i][j + 1] - pref[i][j] + x;
    }
  }
  for (int i = 0; i <= k; i++) {
    for (int j = 0; j < n; j++) {
      dp[i][j] = 2e9;
    }
  }
  for (int i = 0; i < n; i++) {
    dp[1][i] = cnt(0, i);
  }
  for (int i = 2; i <= k; i++) {
    f(i, 0, n, 1, n - 1);
  }
  int res = INT32_MAX;
  for (int i = 1; i <= k; i++) {
    res = min(res, dp[i][n - 1]);
  }
  print_int(res);
}
