#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx,avx2,sse,sse2")
using namespace std;
const int INF = 0x3f3f3f3f;
const long long mod = 1e9 + 7;
const int N = 4005;
const int BUFSIZE = 50 << 20;
char Buf[BUFSIZE + 1], *buf = Buf;
template <class T>
inline void read(T& a) {
  for (a = 0; *buf < '0' || *buf > '9'; buf++)
    ;
  while (*buf >= '0' && *buf <= '9') {
    a = a * 10 + (*buf - '0');
    buf++;
  }
}
int a[N][N], pre[N][N], s[N][N];
int f[805][N];
struct Node {
  int j, x, y;
} q[N];
int cal(int u, int j, int i) { return f[u - 1][j] + s[j + 1][i]; }
void work(int u, int n) {
  int l = 0, r = -1;
  q[++r] = {0, 1, n};
  for (int i = 1; i <= n; i++) {
    while (q[l].y < i) l++;
    f[u][i] = cal(u, q[l].j, i);
    if (i == n) break;
    q[l].x = i + 1;
    while (1) {
      if (l > r) {
        q[++r] = {i, i + 1, n};
        break;
      }
      if (cal(u, i, q[r].x) <= cal(u, q[r].j, q[r].x)) {
        r--;
      } else {
        int L = q[r].x, R = q[r].y + 1;
        while (L < R) {
          int mid = L + R >> 1;
          if (cal(u, i, mid) <= cal(u, q[r].j, mid))
            R = mid;
          else
            L = mid + 1;
        }
        q[r].y = L - 1;
        if (L <= n) q[++r] = {i, L, n};
        break;
      }
    }
  }
}
int main() {
  fread(Buf, 1, BUFSIZE, stdin);
  int n, m;
  read(n), read(m);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
      read(a[i][j]);
      pre[i][j] = pre[i][j - 1] + a[i][j];
    }
  }
  for (int i = 1; i <= n; i++) {
    for (int j = i + 1; j <= n; j++) {
      s[i][j] = s[i][j - 1] + pre[j][j - 1] - pre[j][i - 1];
    }
  }
  memset(f, 0x3f, sizeof f);
  f[0][0] = 0;
  for (int u = 1; u <= m; u++) {
    work(u, n);
  }
  printf("%d\n", f[m][n]);
  return 0;
}
