#include <bits/stdc++.h>
using namespace std;
const int maxN = 4005;
const int maxK = 805;
const long long INF = 1000000000000000000LL;
int read() {
  int num = 0;
  char c;
  while (!isdigit(c = getchar()))
    ;
  num = c - '0';
  while (isdigit(c = getchar())) num = num * 10 + c - '0';
  return num;
}
int n, k;
long long sum[maxN][maxN];
long long dp[maxK][maxN];
int pos[maxK][maxN];
void load() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      int x;
      x = read();
      sum[i][j] = sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1] + x;
    }
  }
}
inline long long get(int x, int y) {
  return sum[y][y] - sum[x - 1][y] - sum[y][x - 1] + sum[x - 1][x - 1];
}
void f(int prev, int lo, int hi, int from, int to) {
  if (lo > hi) return;
  int curr = prev + 1;
  int mid = (lo + hi) / 2;
  long long &ret = dp[curr][mid];
  ret = INF;
  int &ret_pos = pos[curr][mid];
  int curr_to = min(to, mid);
  for (int i = curr_to; i >= from; i--) {
    long long result = dp[prev][i - 1] + get(i, mid) / 2;
    if (result < ret) {
      ret = result;
      ret_pos = i;
    }
  }
  f(prev, lo, mid - 1, from, ret_pos);
  f(prev, mid + 1, hi, ret_pos, to);
}
void solve() {
  dp[1][0] = 0;
  for (int i = 1; i <= n; i++) dp[1][i] = get(1, i) / 2;
  for (int i = 2; i <= k; i++) f(i - 1, 1, n, 1, n);
  printf("%I64d\n", dp[k][n]);
}
int main(void) {
  load();
  solve();
  return 0;
}
