#include <bits/stdc++.h>
using namespace std;
inline int Scan() {
  int res = 0, ch, flag = 0;
  if ((ch = getchar()) == '-')
    flag = 1;
  else if (ch >= '0' && ch <= '9')
    res = ch - '0';
  while ((ch = getchar()) >= '0' && ch <= '9') res = res * 10 + ch - '0';
  return flag ? -res : res;
}
int u[4005][4005], cost[4005][4005];
inline int get_cost(int i, int j) {
  return (cost[j][j] - cost[i - 1][j] - cost[j][i - 1] + cost[i - 1][i - 1]) /
         2;
}
int dp[805][4005];
void solve(int d, int l, int r, int optl, int optr) {
  if (l > r) return;
  if (l == r) {
    dp[d][l] = 0x3f3f3f3f;
    for (int i = optl; i <= optr; ++i)
      dp[d][l] = min(dp[d][l], dp[d - 1][i] + get_cost(i + 1, l));
    return;
  }
  int k, mid = (l + r) >> 1;
  dp[d][mid] = 0x3f3f3f3f;
  for (int i = optl; i <= optr; ++i) {
    int tmp = dp[d - 1][i] + get_cost(i + 1, mid);
    if (tmp < dp[d][mid]) {
      dp[d][mid] = tmp;
      k = i;
    }
  }
  solve(d, l, mid - 1, optl, k);
  solve(d, mid + 1, r, k, optr);
}
int main() {
  int n, K;
  scanf("%d%d", &n, &K);
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j) u[i][j] = Scan();
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
      cost[i][j] =
          cost[i - 1][j] + cost[i][j - 1] - cost[i - 1][j - 1] + u[i][j];
  for (int i = 1; i <= n; ++i) dp[1][i] = get_cost(1, i);
  for (int i = 2; i <= K; ++i) solve(i, 1, n, 0, n - 1);
  printf("%d\n", dp[K][n]);
  return 0;
}
