#include <bits/stdc++.h>
using namespace std;
int dx[] = {0, 0, 1, -1, 1, -1, 1, -1}, dy[] = {-1, 1, 0, 0, 1, -1, -1, 1};
void run();
int main() {
  ios::sync_with_stdio(0);
  run();
}
const int BUFSIZE = 1 << 16;
static char outbuf[BUFSIZE];
int outbuf_size = 0;
void init_io() { ios_base::sync_with_stdio(false); }
void flush() {
  fwrite(outbuf, outbuf_size, 1, stdout);
  outbuf_size = 0;
}
template <typename T>
bool read_num(T &x) {
  register int c = getchar();
  x = 0;
  bool neg = false;
  while (!isdigit(c) && c != '-' && c != EOF) c = getchar();
  if (c == EOF) return false;
  if (c == '-') {
    neg = true;
    c = getchar();
  }
  while (isdigit(c)) {
    x = x * 10 + c - '0';
    c = getchar();
  }
  if (neg) x = -x;
  return true;
}
void write_char(char c) {
  if (outbuf_size == BUFSIZE) flush();
  outbuf[outbuf_size++] = c;
}
void write_str(const char *c) {
  while (*c) write_char(*(c++));
}
bool unwrite() {
  if (!outbuf_size) return false;
  outbuf_size--;
  return true;
}
template <typename T>
void write_num(T x) {
  if (x < 0) {
    write_char('-');
    x = -x;
  }
  static int digs[25];
  register int i = 0;
  while (x) {
    digs[i++] = x % 10;
    x /= 10;
  }
  if (i) {
    while (i) {
      write_char(digs[i - 1] + '0');
      --i;
    }
  } else
    write_char('0');
}
const int inf = 0x3f3f3f3f;
int n, k;
int u[4444][4444];
int f[888][4444];
int S[4444][4444];
int C[4444][4444];
void solve(int i, int lo, int hi, int optLo, int optHi) {
  if (lo > hi) return;
  int mid = (lo + hi) / 2;
  int best = f[i - 1][optLo] + C[optLo + 1][mid], bestj = optLo;
  for (int j = optLo + 1; j <= min(optHi, mid - 1); ++j) {
    int val = f[i - 1][j] + C[j + 1][mid];
    if (val < best) {
      best = val;
      bestj = j;
    }
  }
  f[i][mid] = best;
  solve(i, lo, mid - 1, optLo, bestj);
  solve(i, mid + 1, hi, bestj, optHi);
}
void run() {
  init_io();
  read_num(n);
  read_num(k);
  memset(f, 0x3f, sizeof f);
  for (int i = (1); i < (n + 1); ++i)
    for (int j = (1); j < (n + 1); ++j) read_num(u[i][j]);
  for (int i = (1); i < (n + 1); ++i)
    for (int j = (1); j < (n + 1); ++j) S[i][j] = S[i][j - 1] + u[i][j];
  for (int i = (1); i < (n + 1); ++i)
    for (int j = (i + 1); j < (n + 1); ++j)
      C[i][j] = C[i][j - 1] + S[j][j - 1] - S[j][i - 1];
  f[0][0] = 0;
  for (int i = (1); i < (k + 1); ++i) solve(i, 1, n, 0, inf);
  write_num(f[k][n]);
  flush();
}
