#include <bits/stdc++.h>
using namespace std;
template <typename T1, typename T2>
bool umin(T1& x, const T2& y) {
  return (x > y ? (x = y, true) : false);
}
template <typename T1, typename T2>
bool umax(T1& x, const T2& y) {
  return (x < y ? (x = y, true) : false);
}
template <typename T>
void read(T& x) {
  char ch;
  T p = 1;
  x = 0;
  do {
    ch = getchar();
  } while (ch <= ' ');
  if (ch == '-') p = -1, ch = getchar();
  while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar();
  x *= p;
}
void read(string& x) {
  char ch;
  do {
    ch = getchar();
  } while (ch <= ' ');
  while (ch > ' ') x += ch, ch = getchar();
}
void read(char& x) {
  do {
    x = getchar();
  } while (x <= ' ');
}
template <typename T, typename... R>
void read(T& x, R&... y) {
  read(x);
  read(y...);
}
const int N = (int)4e3 + 3;
const int INF = (int)1e9 + 17;
const long long mod = (long long)1e9 + 7;
const long long LLINF = (long long)1e18 + 17;
const long double pi = (long double)acos(-1.0);
int n, m;
int f[N][N];
int dp[803][N];
int pref[N][N];
int cost[N][N];
int sum(int* pref, int l, int r) { return pref[r] - (l > 0 ? pref[l - 1] : 0); }
void solve(int p, int l, int r, int tl, int tr) {
  if (l > r) return;
  int m = (l + r) / 2;
  int idx = 0;
  for (int i = (tl); i < (tr + 1); i++) {
    if (umin(dp[p][m], dp[p - 1][i] + cost[i + 1][m])) {
      idx = i;
    }
  }
  solve(p, l, m - 1, tl, idx);
  solve(p, m + 1, r, idx, tr);
}
int main() {
  read(n, m);
  for (int i = (0); i < (n); i++)
    for (int j = (0); j < (n); j++) {
      read(f[i][j]);
    }
  for (int i = (0); i < (n); i++)
    for (int j = (0); j < (n); j++) {
      pref[i][j] = f[i][j] + (j > 0 ? pref[i][j - 1] : 0);
    }
  for (int l = (0); l < (n); l++)
    for (int r = (l + 1); r < (n); r++) {
      cost[l][r] = cost[l][r - 1] + sum(pref[r], l, r);
    }
  fill(dp[1], dp[m + 1], INF);
  for (int i = (0); i < (n); i++) dp[1][i] = cost[0][i];
  for (int layer = (2); layer < (m + 1); layer++)
    solve(layer, 0, n - 1, 0, n - 1);
  printf("%d\n", dp[m][n - 1]);
  return 0;
}
