#include <bits/stdc++.h>
using namespace std;
int dp[4010][810];
int s[4010][810];
int n, m;
int a[4010][4010];
int f[4010][4010];
int val[4010][4010];
int main() {
  scanf("%d %d", &n, &m);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++) {
      scanf("%d", &a[i][j]);
      f[i][j] = f[i - 1][j] + f[i][j - 1] - f[i - 1][j - 1] + a[i][j];
    }
  for (int i = 1; i <= n; i++)
    for (int j = i; j <= n; j++)
      val[i][j] = (f[j][j] - f[j][i - 1] - f[i - 1][j] + f[i - 1][i - 1]) / 2;
  memset(dp, 0x3f, sizeof(dp));
  dp[0][0] = 0;
  for (int j = 1; j <= m; j++) {
    s[n + 1][j] = n;
    for (int i = n; i >= 1; i--) {
      for (int k = s[i][j - 1]; k <= s[i + 1][j]; k++)
        if (dp[k][j - 1] + val[k + 1][i] < dp[i][j]) {
          dp[i][j] = dp[k][j - 1] + val[k + 1][i];
          s[i][j] = k;
        }
    }
  }
  printf("%d\n", dp[n][m]);
  return 0;
}
