#include <bits/stdc++.h>
using namespace std;
const string nameFile = "test";
ifstream in(nameFile + ".in");
ofstream out(nameFile + ".out");
const int nmax = 4e3;
int n, nrGond;
char ch;
int a[nmax + 2][nmax + 2];
int dp[802][nmax + 2];
char buffer[10000];
inline int getCost(int i, int j) {
  return (a[j][j] + a[i - 1][i - 1] - a[j][i - 1] - a[i - 1][j]) / 2;
}
void divideDp(int ll, int rr, int limLeftSrc, int limRightSrc, int layer) {
  if (ll > rr) return;
  int mij = (ll + rr) / 2;
  pair<int, int> ob = {1e9, 0};
  for (int i = limLeftSrc; i <= min(mij, limRightSrc); i++)
    ob = min(ob, {getCost(i, mij) + dp[layer - 1][i - 1], i});
  dp[layer][mij] = ob.first;
  divideDp(ll, mij - 1, limLeftSrc, ob.second, layer);
  divideDp(mij + 1, rr, ob.second, limRightSrc, layer);
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(0);
  cout.tie(0);
  scanf("%d%d\n", &n, &nrGond);
  for (int i = 1; i <= n; i++) {
    gets(buffer);
    for (int j = 1; j <= n; j++)
      a[i][j] = buffer[2 * (j - 1)] - '0' + a[i - 1][j] + a[i][j - 1] -
                a[i - 1][j - 1];
  }
  for (int i = 1; i <= n; i++) dp[0][i] = 1e9;
  for (int i = 1; i <= nrGond; i++) divideDp(i, n, i, n, i);
  cout << dp[nrGond][n];
  return 0;
}
