#include <bits/stdc++.h>
using namespace std;
inline char gc() {
  static char now[1 << 16], *S, *T;
  if (T == S) {
    T = (S = now) + fread(now, 1, 1 << 16, stdin);
    if (T == S) return EOF;
  }
  return *S++;
}
inline int read() {
  int x = 0, f = 1;
  char ch = gc();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = gc();
  }
  while (isdigit(ch)) x = x * 10 + ch - '0', ch = gc();
  return x * f;
}
const int N = 4040;
const int inf = 0x3f3f3f3f;
int n, k, sum, s[N][N], K, dp[N][1000], q[N];
inline int gao(int x, int y) { return s[y][y] - s[y][x]; }
inline int calc(int x, int y) {
  int l = y + 1, r = n, res = n + 1;
  while (l <= r) {
    int mid = l + r >> 1;
    if (dp[x][k - 1] + gao(x, mid) >= dp[y][k - 1] + gao(y, mid))
      res = mid, r = mid - 1;
    else
      l = mid + 1;
  }
  return res;
}
int main() {
  n = read();
  K = read();
  sum = 0;
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
      if (j <= i)
        s[i][j] = read(), sum += s[i][j];
      else
        read();
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= i; ++j) s[i][j] += s[i - 1][j];
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= i; ++j) s[i][j] += s[i][j - 1];
  for (int i = 0; i <= n; ++i) dp[i][0] = inf;
  dp[0][0] = 0;
  for (k = 1; k <= K; ++k) {
    int op = 1, cl = 1;
    q[op] = 0;
    for (int i = 1, j; i <= n; ++i) {
      while (op < cl && calc(q[op], q[op + 1]) <= i) ++op;
      j = q[op];
      dp[i][k] = dp[j][k - 1] + gao(j, i);
      while (op < cl && calc(q[cl - 1], q[cl]) >= calc(q[cl], i)) --cl;
      q[++cl] = i;
    }
  }
  printf("%d\n", dp[n][K]);
  return 0;
}
