#include <bits/stdc++.h>
#pragma GCC target("avx")
#pragma GCC optimize("Ofast,O3,O2,unroll-loops")
using namespace std;
using UL = unsigned long int;
using UI = unsigned int;
using ULL = unsigned long long int;
using LI = long int;
using LL = long long;
using LF = double;
using LLF = long double;
const int MOD1 = 1000000007;
const int inf = 0x3f3f3f3f;
const double PI = acos(-1);
int binoMax = 10000;
vector<LL> numInv(binoMax + 1), factNumInv(binoMax + 1), fact(binoMax + 1);
vector<LL> little_primes = {2, 3, 5, 7, 11, 13, 17, 19, 23, 31, 37};
template <typename T>
T extgcd(T a, LL b, T &x, T &y) {
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  }
  T d = extgcd(b, a % b, y, x);
  y -= (a / b * x);
  return d;
}
template <typename T>
T mod_inv(T a, T p) {
  if (__gcd(a, p) != 1) return -1;
  T x, y;
  extgcd(a, p, x, y);
  x %= p;
  if (x < 0) x += p;
  return x;
}
inline void generate_ncrp(LL p) {
  int i;
  numInv[0] = numInv[1] = 1;
  for (i = 2; i <= binoMax; i++) {
    numInv[i] = numInv[p % i] * (p - p / i) % p;
  }
  factNumInv[0] = factNumInv[1] = 1;
  for (i = 2; i <= binoMax; i++) {
    factNumInv[i] = (numInv[i] * factNumInv[i - 1]) % p;
  }
  fact[0] = 1;
  for (i = 1; i <= binoMax; i++) {
    fact[i] = (fact[i - 1] * i) % p;
  }
}
LL ncrmodp(LL n, LL r, LL p) {
  LL ans = ((fact[n] * factNumInv[r]) % p * factNumInv[n - r]) % p;
  return ans;
}
LL powM(LL x, LL y, LL p) {
  LL res = 1;
  while (y > 0) {
    if (y & 1) res = (res * x) % p;
    y = y >> 1;
    x = (x * x) % p;
  }
  return res;
}
struct Matrix {
  int row, col;
  vector<vector<LL>> a;
  Matrix(int r, int c) {
    row = r;
    col = c;
    a.resize(row, vector<LL>(col, 0));
    ;
  }
  static Matrix IDM(LL n) {
    Matrix res(n, n);
    for (int i = 0; i < n; i++) res.a[i][i] = 1;
    return res;
  }
};
Matrix Matmult(Matrix A, Matrix B) {
  Matrix res(A.row, B.col);
  LL i, j, k;
  for (i = 0; i <= A.row - 1; i++) {
    for (j = 0; j <= B.col - 1; j++) {
      for (k = 0; k <= A.col - 1; k++) {
        res.a[i][j] = (res.a[i][j] + A.a[i][k] * B.a[k][j]) % MOD1;
      }
    }
  }
  return res;
}
Matrix BinExp(Matrix X, LL n) {
  Matrix res = Matrix::IDM(X.row);
  while (n > 0) {
    if (n & 1) {
      res = Matmult(X, res);
    }
    X = Matmult(X, X);
    n >>= 1;
  }
  return res;
}
LL k, n;
LL dp[805][4005];
LL um[4001][4001];
LL cost(int l, int r) {
  return (um[r][r] - um[l - 1][r] - um[r][l - 1] + um[l - 1][l - 1]) >> 1;
}
inline void calc(int i, int jl, int jr, int kl, int kr) {
  if (jl > jr) return;
  int jm = (jl + jr) >> 1, k;
  pair<LL, int> best = {INT_MAX, -1};
  for (k = max(i - 1, kl); k <= min(jm - 1, kr); k++) {
    best = min(best, {dp[i - 1][k] + cost(k + 1, jm), k});
  }
  dp[i][jm] = best.first;
  int sp = best.second;
  calc(i, jl, jm - 1, kl, sp);
  calc(i, jm + 1, jr, sp, kr);
}
int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
  LL i, j, x, y, ntc, left, right, optl, optr;
  char inp;
  cin >> n >> k;
  for (i = 1; i <= n; i++) {
    for (j = 1; j <= n; j++) {
      cin >> inp;
      x = inp - '0';
      um[i][j] = (um[i - 1][j] + um[i][j - 1] - um[i - 1][j - 1] + x);
    }
  }
  for (i = 1; i <= n; i++) dp[1][i] = cost(1, i);
  for (i = 2; i <= k; i++) {
    calc(i, 1, n, 1, n);
  }
  cout << dp[k][n];
}
