#include <bits/stdc++.h>
using namespace std;
const int N = 4005, K = 808;
const int oo = 1e9;
int mat[N][N];
int C[N][N];
int dp[N][2];
int cnt;
void solve(int L, int R, int l, int r, int k) {
  if (L > R) return;
  int mid = (L + R) / 2;
  int opt = mid;
  dp[mid][k] = dp[mid + 1][1 - k];
  for (int j = max(mid, l); j <= r; j++) {
    int cand = C[mid][j] + dp[j + 1][1 - k];
    if (cand < dp[mid][k]) {
      dp[mid][k] = cand;
      opt = j;
    }
  }
  solve(L, mid - 1, l, opt, k);
  solve(mid + 1, R, opt, r, k);
}
int n, k;
int main() {
  scanf("%d %d", &n, &k);
  getchar();
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
      mat[i][j] = int(getchar() - '0');
      getchar();
      mat[i][j] += mat[i - 1][j] + mat[i][j - 1] - mat[i - 1][j - 1];
    }
  for (int i = 1; i <= n; i++)
    for (int j = i; j <= n; j++) {
      C[i][j] = mat[j][j] - mat[j][i - 1] - mat[i - 1][j] + mat[i - 1][i - 1];
      C[i][j] /= 2;
    }
  for (int i = 1; i <= n; i++) dp[i][0] = oo;
  for (int j = 1; j <= k; j++) {
    solve(1, n, 1, n, j % 2);
  }
  printf("%d\n", dp[1][k % 2]);
}
