#include <bits/stdc++.h>
using namespace std;
const int inf = 1e9;
const int maxn = 4e3 + 7;
int sum[maxn][maxn];
int dp[2][maxn];
bool turn;
inline int get_sum(int l, int r) {
  if (l > r) return 0;
  return sum[r][r] - sum[r][l - 1] - sum[l - 1][r] + sum[l - 1][l - 1];
}
inline int cut_cost(int k, int i) {
  return dp[turn ^ 1][k] + get_sum(k + 1, i);
}
void solve(int l, int r, int optl, int optr) {
  if (l > r) return;
  int m = (l + r) >> 1;
  int optm = optl;
  for (int opt = optl; opt <= min(m - 1, optr); ++opt) {
    long long new_cost = cut_cost(opt, m);
    long long cur_cost = cut_cost(optm, m);
    if (new_cost < cur_cost) optm = opt;
  }
  dp[turn][m] = cut_cost(optm, m);
  solve(l, m - 1, optl, optm);
  solve(m + 1, r, optm, optr);
}
void fastscan(int &number) {
  bool negative = false;
  register int c;
  number = 0;
  c = getchar();
  if (c == '-') {
    negative = true;
    c = getchar();
  }
  for (; (c > 47 && c < 58); c = getchar()) number = number * 10 + c - 48;
  if (negative) number *= -1;
}
int main() {
  int n, k;
  fastscan(n);
  fastscan(k);
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
      fastscan(sum[i][j]),
          sum[i][j] += sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1];
  for (int i = 0; i < 2; ++i)
    for (int j = 0; j < maxn; ++j) dp[i][j] = inf;
  for (int i = 1; i <= n; ++i) dp[turn][i] = get_sum(1, i);
  for (int i = 2; i <= k; ++i) turn ^= 1, solve(i - 1, n, i - 1, n);
  printf("%d", dp[turn][n] / 2);
}
