#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline string toString(T a) {
  ostringstream os("");
  os << a;
  return os.str();
}
template <typename T>
inline long long toLong(T a) {
  long long res;
  istringstream os(a);
  os >> res;
  return res;
}
template <typename T>
inline T SQ(T a) {
  return a * a;
}
template <typename T>
inline T gcd(T a, T b) {
  if (b == 0)
    return a;
  else
    return gcd(b, a % b);
}
template <typename T>
inline unsigned long long bigmod(T a, T b, T m) {
  if (b == 0)
    return 1;
  else if (b % 2 == 0)
    return SQ(bigmod(a, b / 2, m)) % m;
  else
    return (a % m * bigmod(a, b - 1, m)) % m;
}
template <typename T>
inline vector<string> parse(T str) {
  vector<string> res;
  string s;
  istringstream os(str);
  while (os >> s) res.push_back(s);
  return res;
}
template <typename T>
inline unsigned long long dist(T A, T B) {
  unsigned long long res =
      (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y);
  return res;
}
template <typename T>
inline double cosAngle(T a, T b, T c) {
  double res = a * a + b * b - c * c;
  res = res / (2 * a * b);
  res = acos(res);
  return res;
}
template <typename T>
inline T power(T base, int po) {
  T res = 1;
  if (base == 0) return 0;
  for (int i = (0); i < (po); i++) res *= base;
  return res;
}
template <typename T>
inline bool isOn(T mask, T pos) {
  return mask & (1 << pos);
}
template <typename T>
inline int Off(T mask, T pos) {
  return mask ^ (1 << pos);
}
template <typename T>
inline int On(T mask, T pos) {
  return mask | (1 << pos);
}
int N, K;
int dp[805][4005];
int mat[4005][4005];
int sum[4005][4005], row[4007];
int cost(int i, int j) {
  i++, j++;
  if (i > j) swap(i, j);
  return sum[j][j] + sum[i - 1][i - 1] - sum[i - 1][j] - sum[j][i - 1];
}
void solve(int k, int l, int r, int x, int y) {
  if (l > r) return;
  int mid = (l + r) / 2, idx;
  int cur, mn;
  if (k == 1)
    dp[k][mid] = cost(0, mid);
  else {
    dp[k][mid] = INT_MAX / 3;
    mn = min(mid, y);
    for (int i = x; i <= mn; i++) {
      cur = dp[k - 1][i] + cost(i + 1, mid);
      if (cur < dp[k][mid]) {
        dp[k][mid] = cur;
        idx = i;
      }
    }
  }
  if (l == r) return;
  if (l < mid) solve(k, l, mid - 1, x, idx);
  if (r > mid) solve(k, mid + 1, r, idx, y);
}
int main() {
  std::ios_base::sync_with_stdio(false);
  int i, j, k;
  int x, y;
  cin >> N >> K;
  for (i = 1; i <= N; i++) {
    for (j = 1; j <= N; j++) {
      cin >> mat[i][j];
    }
  }
  for (i = 1; i <= N; i++) {
    for (j = 1; j <= N; j++) {
      sum[i][j] =
          (mat[i][j] + sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1]);
    }
  }
  for (i = 1; i <= K; i++) {
    solve(i, 0, N - 1, 0, N - 1);
  }
  cout << dp[K][N - 1] / 2 << endl;
}
