#include <bits/stdc++.h>
using namespace std;
const int oo = (int)1e8;
vector<vector<int>> groupCosts;
void solveDP(vector<int>& oldDP, vector<int>& newDP, int L, int R, int L1,
             int R1) {
  if (R < L) return;
  int mid = (L + R) / 2;
  int res = oo, pos = L1;
  for (int i = L1; i <= min(mid, R1); i++) {
    int now = groupCosts[i][mid];
    int curCost = now + (i ? oldDP[i - 1] : 0);
    if (curCost < res) {
      res = curCost;
      pos = i;
    }
  }
  newDP[mid] = res;
  solveDP(oldDP, newDP, L, mid - 1, L1, pos);
  solveDP(oldDP, newDP, mid + 1, R, pos, R1);
}
void solve() {
  int n, k;
  cin >> n >> k;
  vector<vector<int>> costs(n, vector<int>(n));
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < n; j++) {
      cin >> costs[i][j];
      if (j) costs[i][j] += costs[i][j - 1];
    }
  }
  groupCosts.resize(n, vector<int>(n));
  for (int i = 0; i < n; i++) {
    for (int j = i + 1; j < n; j++) {
      groupCosts[i][j] += groupCosts[i][j - 1];
      groupCosts[i][j] += costs[j][j - 1] - (i ? costs[j][i - 1] : 0);
    }
  }
  vector<int> oldDP(n, oo);
  for (int curK = 0; curK < k; curK++) {
    vector<int> newDP(n, oo);
    solveDP(oldDP, newDP, curK, n - 1, 0, n - 1);
    swap(oldDP, newDP);
  }
  cout << oldDP[n - 1] << '\n';
}
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  cout.tie(NULL);
  solve();
  return 0;
}
