#include <bits/stdc++.h>
std::mt19937_64 rng(
    std::chrono::steady_clock::now().time_since_epoch().count());
int myRand(int R) {
  int val = rng() % R;
  assert(val >= 0);
  return val;
}
const long double PI = atan(1.0) * 4;
const int32_t INF32 = 2e9 + 7;
const int64_t INF64 = 3e18;
const int32_t LOG = 21;
const int32_t MOD = 1e9 + 7;
using namespace std;
void my_debugger(string second, int LINE_NUM) { cerr << '\n'; }
template <typename start, typename... end>
void my_debugger(string second, int LINE_NUM, start x, end... y) {
  if (second.back() != ',') {
    second += ',';
    cerr << "LINE(" << LINE_NUM << "): ";
  }
  int i = second.find(',');
  cerr << second.substr(0, i) << " = " << x;
  second = second.substr(i + 1);
  if (!second.empty()) cerr << ", ";
  my_debugger(second, LINE_NUM, y...);
}
int dp[805][4005];
int cost[4005][4005];
int a[4005][4005];
inline void solve(int i, int l, int r, int kl, int kr) {
  if (l > r) return;
  int mid = (l + r) >> 1;
  int best_k = -1;
  for (int k = kl; k < (int)kr + 1; k++) {
    if (best_k == -1 || dp[i][mid] > dp[i - 1][k] + cost[k + 1][mid]) {
      dp[i][mid] = dp[i - 1][k] + cost[k + 1][mid];
      best_k = k;
    }
  }
  solve(i, l, mid - 1, kl, best_k);
  solve(i, mid + 1, r, best_k, kr);
}
int32_t main() {
  ios_base::sync_with_stdio(false), cin.tie(nullptr);
  int tests = 1;
  for (int ii = 0; ii < (int)tests; ii++) {
    int n, k;
    cin >> n >> k;
    for (int i = 1; i < (int)n + 1; i++) {
      for (int j = 1; j < (int)n + 1; j++) {
        cin >> a[i][j];
        a[i][j] += a[i][j - 1];
      }
    }
    for (int i = 1; i < (int)n + 1; i++)
      for (int j = 1; j < (int)n + 1; j++) cost[i][i] = 0;
    for (int len = 2; len < (int)n + 1; len++) {
      for (int i = 1; i < (int)n + 1; i++) {
        int j = i + len - 1;
        if (j > n) break;
        cost[i][j] = cost[i + 1][j] + a[i][j] - a[i][i];
      }
    }
    for (int j = 1; j < (int)n + 1; j++) dp[1][j] = cost[1][j];
    for (int i = 2; i < (int)k + 1; i++) solve(i, 1, n, 1, n);
    cout << dp[k][n] << '\n';
  }
  return 0;
}
