#include <bits/stdc++.h>
using namespace std;
const int N = 4004;
int n, k, dp[2][N], s[N][N];
int sum(int x, int y) {
  return (s[x][x] - s[x][y - 1] - s[y - 1][x] + s[y - 1][y - 1]);
}
void solve(int l, int r, int x, int y) {
  if (l > r) {
    return;
  }
  int mid = (l + r) / 2;
  int M;
  for (int i = min(mid, y); i >= x; i--) {
    if (dp[1][mid] >= sum(mid, i) + dp[0][i - 1]) {
      dp[1][mid] = sum(mid, i) + dp[0][i - 1];
      M = i;
    }
  }
  if (l == r) {
    return;
  }
  solve(l, mid - 1, x, M);
  solve(mid + 1, r, M, y);
}
int main() {
  scanf("%d%d", &n, &k);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
      int x;
      scanf("%d", &x);
      s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + x;
    }
  for (int i = 1; i <= n; i++) {
    dp[0][i] = s[i][i];
    dp[1][i] = 1e9;
  }
  for (int j = 2; j <= k; j++) {
    solve(1, n, 1, n);
    for (int j = 0; j <= n; j++) {
      dp[0][j] = dp[1][j], dp[1][j] = 1e9;
    }
    dp[1][0] = 0;
  }
  dp[0][n] /= 2;
  printf("%d", dp[0][n]);
}
