#include <bits/stdc++.h>
using namespace std;
int read() {
  int out = 0;
  char c;
  while (!isdigit(c = getchar()))
    ;
  for (; isdigit(c); c = getchar()) out = out * 10 + c - '0';
  return out;
}
const int N = 4010;
const int K = 810;
int n, m, pre[N][N], f[K][N];
int calc(int i, int j, int k) {
  return f[j - 1][k] + pre[k - 1][k - 1] - pre[i - 1][k - 1];
}
void solve(int l, int r, int L, int R, int j) {
  int mid = ((l + r) >> 1);
  int opt = R, optres = calc(mid, j, R);
  for (int i = max(L, mid + 1); i < R; ++i) {
    int res = calc(mid, j, i);
    if (res < optres) {
      opt = i;
      optres = res;
    }
  }
  f[j][mid] = optres;
  if (l == r - 1) return;
  solve(l, mid, L, opt, j);
  solve(mid, r, opt, R, j);
}
int main() {
  n = read();
  m = read();
  for (int i = 1; i <= n; ++i) {
    for (int j = 1; j <= n; ++j) {
      pre[i][j] = pre[i][j - 1] + pre[i - 1][j] - pre[i - 1][j - 1];
      if (i < j)
        pre[i][j] += read();
      else
        read();
    }
  }
  memset(f, 0x3f, sizeof(f));
  f[0][n + 1] = 0;
  for (int i = 1; i <= m; ++i) solve(1, n + 1, 1, n + 1, i);
  cout << f[m][1];
  return 0;
}
