#include <bits/stdc++.h>
#pragma GCC optimize("O2")
using namespace std;
void rit(int &n) {
  char c;
  while (!isdigit(c = getchar()))
    ;
  n = c - '0';
  while (isdigit(c = getchar())) n = n * 10 + c - '0';
}
void rc(int &n) {
  char c;
  while (!isdigit(c = getchar()))
    ;
  n = c - '0';
}
int u[4005][4005], arr[4005][4005], dp[805][4005];
int ck;
void f(int l, int r, int ql, int qr) {
  if (l > r) return;
  int m = (l + r) >> 1, mn = 1e9, mni = -1;
  for (int i = ql; i <= qr && i < m; i++) {
    if (dp[ck - 1][i] + arr[i + 1][m] < mn) {
      mn = dp[ck - 1][i] + arr[i + 1][m];
      mni = i;
    }
  }
  dp[ck][m] = mn;
  f(l, m - 1, ql, mni);
  f(m + 1, r, mni, qr);
}
int main() {
  cin.tie(0), ios::sync_with_stdio(0);
  int n, k;
  rit(n);
  rit(k);
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) rc(u[i][j]);
  }
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) u[i][j] += u[i][j - 1];
  }
  for (int i = 1; i <= n; i++) {
    int s = 0;
    for (int j = i + 1; j <= n; j++) {
      s += u[j][j] - u[j][i - 1];
      arr[i][j] = s;
    }
  }
  for (int i = 1; i <= n; i++) dp[1][i] = arr[1][i];
  for (int i = 2; i <= k; i++) ck = i, f(1, n, 0, n);
  cout << dp[k][n] << "\n";
  return 0;
}
