#include <bits/stdc++.h>
using namespace std;
const int INF = 1e9 + 10;
vector<vector<int>> S, DP;
void calc(int i, int l, int r, int optMin, int optMax) {
  int m = (l + r) / 2;
  int vMin = INF;
  int opt = -1;
  for (int a = optMin; a <= min(optMax, r); a++) {
    int v = DP[i - 1][a - 1] + S[m][m] - S[m][a - 1] - S[a - 1][m] +
            S[a - 1][a - 1];
    if (vMin > v) {
      vMin = v;
      opt = a;
    }
  }
  DP[i][m] = vMin;
  if (l != r) {
    calc(i, l, m, optMin, opt);
    calc(i, m + 1, r, opt, optMax);
  }
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  int n, k;
  cin >> n >> k;
  S = vector<vector<int>>(n + 1, vector<int>(n + 1));
  DP = vector<vector<int>>(k + 1, vector<int>(n + 1, INF));
  DP[0][0] = 0;
  for (int i = 1; i <= n; i++) {
    int r = 0;
    for (int j = 1; j <= n; j++) {
      int u;
      cin >> u;
      r += u;
      S[i][j] = S[i - 1][j] + r;
    }
  }
  for (int i = 1; i <= k; i++) {
    calc(i, i, n, 1, n);
  }
  cout << DP[k][n] / 2 << endl;
  return 0;
}
