#include <bits/stdc++.h>
using namespace std;
template <typename T>
T gcd(T a, T b) {
  return b == 0 ? a : gcd(b, a % b);
}
template <typename T>
T lcm(T a, T b) {
  return a / gcd(a, b) * b;
}
template <typename T>
T ext_gcd(T a, T b, T& first, T& second) {
  if (b == 0) {
    first = 1, second = 0;
    return a;
  }
  T d = ext_gcd(b, a % b, second, first);
  second -= first * (a / b);
  return d;
}
template <typename T>
T inverse(T a, T n) {
  T first, second;
  T t = ext_gcd(a, n, first, second);
  if (t != 1) return -1;
  return first < 0 ? first + n : first;
}
template <typename T>
T Q_mul(T a, T b, T Mod) {
  T ret;
  for (ret = 0; b; b >>= 1, a = (a + a) % Mod)
    if (b & 1) ret = (ret + a) % Mod;
  return ret;
}
template <typename T>
T quick_pow_mod(T a, T b, T Mod) {
  T ret;
  for (ret = 1; b; b >>= 1, (a *= a) %= Mod)
    if (b & 1) (ret *= a) %= Mod;
  return ret;
}
template <typename T>
T quick_pow(T a, T b) {
  T ret;
  for (ret = 1; b; b >>= 1, a *= a)
    if (b & 1) ret *= a;
  return ret;
}
double combination(int n, int r) {
  if (r < n - r) return combination(n, n - r);
  double s = 1.0;
  for (int i = 1; i <= int(n - r); ++i) s *= (r + i), s /= i;
  return s;
}
template <typename T>
inline void read(T& v) {
  T ret = 0, sgnv = 1;
  char p;
  while (!isdigit(p = getchar()))
    if (p == '-') sgnv = -1;
  do ret = (ret << 3) + (ret << 1) + p - '0';
  while (isdigit(p = getchar()));
  v = sgnv * ret;
}
const int INF = 0x7f7f7f7f;
int u[4000 + 5][4000 + 5], w[4000 + 5][4000 + 5], f[2][4000 + 5], c;
inline int getM(int first, int second) {
  return f[c][second] + w[second + 1][first];
}
void row_minima(int first, int second, int n, int m) {
  if (n == 0 || m == 0) return;
  int mid = first + n / 2, mi = getM(mid, second), pos = second;
  for (int i = second + 1; i < second + m && i < mid; ++i)
    if (getM(mid, i) < getM(mid, pos)) mi = getM(mid, i), pos = i;
  row_minima(first, second, n / 2, pos - second + 1),
      row_minima(mid + 1, pos, n - n / 2 - 1, second + m - pos);
  f[c ^ 1][mid] = mi;
}
int main() {
  int n, k;
  read(n), read(k);
  for (int i = 0; i < int(n); ++i)
    for (int j = 0; j < int(n); ++j) read(u[i][j]);
  for (int i = 0; i < int(n); ++i)
    for (int j = int(i - 1); j >= 0; --j) u[i][j] += u[i][j + 1];
  for (int i = 0; i < int(n); ++i)
    for (int j = int(i + 1); j <= int(n - 1); ++j)
      w[i][j] = w[i][j - 1] + u[j][i];
  for (int i = 0; i < int(n); ++i) f[c][i] = w[0][i];
  for (int i = 0; i < int(k - 1); ++i)
    row_minima(i + 1, i, n - i - 1, n - i), c ^= 1;
  printf("%d", f[c][n - 1]);
  return 0;
}
