#include <cstdio>
#include <string>
#include <vector>
#include <algorithm>
#include <memory.h>
#include <cmath>
#include <map>
#include <set>
#include <queue>
#include <stack>
#include <ctime>
#include <iostream>
#include <functional>
#include <complex>
#include <stdlib.h>
#include <fstream>
#include <random>
#include <csignal>
#include <chrono>
#include <bitset>
#include <unordered_set>
#include <unordered_map>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<pii, int> p3i;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef vector<p3i> v3i;
typedef vector<vii> vvii;
typedef vector<p3i> vp3i;
typedef long double ld;
typedef vector<ld> vld;
#define pb push_back
#define mp make_pair
#define REP(i, n) for (int (i) = 0; (i) < (n); (i)++)
#define REPD(i, n) for (int (i) = (n) - 1; (i) >= 0; (i)--)
#define FOR(i, a, b) for (int (i) = (a); (i) < (b); (i)++)
#define FORD(i,a, b) for (int (i) = (a); (i) >= (b); (i)--)
#define sz(v) (int)(v).size()
#define all(v) (v).begin(), (v).end()
#define rv(v) reverse(all(v))
#define CL(v, val) memset((v), (val), sizeof((v)))
#define SORT(a) sort(all(a))
#define un(v) SORT(v), (v).resize(unique(all(v)) - (v).begin())
#define eps 1.0e-9
#define X first
#define Y second
#define bit(n) (1 << (n))
#define bit64(n) (ll(1) << (n))
#define sqr(x) ((x) * (x))
#define sq5(x) ((x) * (x) * (x) * (x) * (x))
#define N 4005
int a[N][N];
int sa[N][N];
int getSum(int lx, int rx, int ly, int ry) {
int res = sa[rx][ry];
if (lx) {
res -= sa[lx - 1][ry];
}
if (ly) {
res -= sa[rx][ly - 1];
}
if (lx && ly) {
res += sa[lx - 1][ly - 1];
}
return res / 2;
}
int dp[N][2];
int Solve(int j, int i) {
int ans = j ? dp[j - 1][0] : 0;
ans += getSum(j, i, j, i);
return ans;
}
int main(void) {
int n, k;
scanf("%d%d", &n, &k);
REP(i, n) {
REP(j, n) {
scanf("%d", &a[i][j]);
sa[i][j] = a[i][j];
if (i) {
sa[i][j] += sa[i - 1][j];
}
if (j) {
sa[i][j] += sa[i][j - 1];
}
if (i && j) {
sa[i][j] -= sa[i - 1][j - 1];
}
}
}
REP(i, n) {
dp[i][0] = getSum(0, i, 0, i);
}
REP(j, k - 1) {
deque<int>q;
q.push_back(0);
dp[0][1] = getSum(0, 0, 0, 0);
FOR(i, 1, n) {
while (sz(q) >= 1) {
int a = Solve(q.back(), i);
int b = Solve(i, i);
if (a <= b) {
break;
}
q.pop_back();
}
q.push_back(i);
while (sz(q) >= 2) {
int a = Solve(q[0], i);
int b = Solve(q[1], i);
if (a <= b) {
break;
}
q.pop_front();
}
dp[i][1] = Solve(q[0], i);
}
REP(i, n) {
dp[i][0] = dp[i][1];
}
}
printf("%d\n", dp[n - 1][0]);
}
I2luY2x1ZGUgPGNzdGRpbz4KI2luY2x1ZGUgPHN0cmluZz4KI2luY2x1ZGUgPHZlY3Rvcj4KI2luY2x1ZGUgPGFsZ29yaXRobT4KI2luY2x1ZGUgPG1lbW9yeS5oPgojaW5jbHVkZSA8Y21hdGg+CiNpbmNsdWRlIDxtYXA+CiNpbmNsdWRlIDxzZXQ+CiNpbmNsdWRlIDxxdWV1ZT4KI2luY2x1ZGUgPHN0YWNrPgojaW5jbHVkZSA8Y3RpbWU+CiNpbmNsdWRlIDxpb3N0cmVhbT4KI2luY2x1ZGUgPGZ1bmN0aW9uYWw+CiNpbmNsdWRlIDxjb21wbGV4PgojaW5jbHVkZSA8c3RkbGliLmg+CiNpbmNsdWRlIDxmc3RyZWFtPgojaW5jbHVkZSA8cmFuZG9tPgojaW5jbHVkZSA8Y3NpZ25hbD4KI2luY2x1ZGUgPGNocm9ubz4gCiNpbmNsdWRlIDxiaXRzZXQ+CiNpbmNsdWRlIDx1bm9yZGVyZWRfc2V0PgojaW5jbHVkZSA8dW5vcmRlcmVkX21hcD4KCnVzaW5nIG5hbWVzcGFjZSBzdGQ7Cgp0eXBlZGVmIGxvbmcgbG9uZyBsbDsKdHlwZWRlZiBwYWlyPGludCwgaW50PiBwaWk7CnR5cGVkZWYgcGFpcjxkb3VibGUsIGRvdWJsZT4gcGRkOwp0eXBlZGVmIHBhaXI8cGlpLCBpbnQ+IHAzaTsKdHlwZWRlZiB2ZWN0b3I8aW50PiB2aTsKdHlwZWRlZiB2ZWN0b3I8cGlpPiB2aWk7CnR5cGVkZWYgdmVjdG9yPHAzaT4gdjNpOwp0eXBlZGVmIHZlY3Rvcjx2aWk+IHZ2aWk7CnR5cGVkZWYgdmVjdG9yPHAzaT4gdnAzaTsKdHlwZWRlZiBsb25nIGRvdWJsZSBsZDsKdHlwZWRlZiB2ZWN0b3I8bGQ+IHZsZDsKCiNkZWZpbmUgcGIgcHVzaF9iYWNrCiNkZWZpbmUgbXAgbWFrZV9wYWlyCiNkZWZpbmUgUkVQKGksIG4pIGZvciAoaW50IChpKSA9IDA7IChpKSA8IChuKTsgKGkpKyspCiNkZWZpbmUgUkVQRChpLCBuKSBmb3IgKGludCAoaSkgPSAobikgLSAxOyAoaSkgPj0gMDsgKGkpLS0pCiNkZWZpbmUgRk9SKGksIGEsIGIpIGZvciAoaW50IChpKSA9IChhKTsgKGkpIDwgKGIpOyAoaSkrKykKI2RlZmluZSBGT1JEKGksYSwgYikgZm9yIChpbnQgKGkpID0gKGEpOyAoaSkgPj0gKGIpOyAoaSktLSkKI2RlZmluZSBzeih2KSAoaW50KSh2KS5zaXplKCkKI2RlZmluZSBhbGwodikgKHYpLmJlZ2luKCksICh2KS5lbmQoKQojZGVmaW5lIHJ2KHYpIHJldmVyc2UoYWxsKHYpKQojZGVmaW5lIENMKHYsIHZhbCkgbWVtc2V0KCh2KSwgKHZhbCksIHNpemVvZigodikpKQojZGVmaW5lIFNPUlQoYSkgc29ydChhbGwoYSkpCiNkZWZpbmUgdW4odikgU09SVCh2KSwgKHYpLnJlc2l6ZSh1bmlxdWUoYWxsKHYpKSAtICh2KS5iZWdpbigpKQojZGVmaW5lIGVwcyAxLjBlLTkKI2RlZmluZSBYIGZpcnN0CiNkZWZpbmUgWSBzZWNvbmQKI2RlZmluZSBiaXQobikgKDEgPDwgKG4pKQojZGVmaW5lIGJpdDY0KG4pIChsbCgxKSA8PCAobikpCiNkZWZpbmUgc3FyKHgpICgoeCkgKiAoeCkpCiNkZWZpbmUgc3E1KHgpICgoeCkgKiAoeCkgKiAoeCkgKiAoeCkgKiAoeCkpCiNkZWZpbmUgTiA0MDA1CgppbnQgYVtOXVtOXTsKaW50IHNhW05dW05dOwoKaW50IGdldFN1bShpbnQgbHgsIGludCByeCwgaW50IGx5LCBpbnQgcnkpIHsKCWludCByZXMgPSBzYVtyeF1bcnldOwoJaWYgKGx4KSB7CgkJcmVzIC09IHNhW2x4IC0gMV1bcnldOwoJfQoJaWYgKGx5KSB7CgkJcmVzIC09IHNhW3J4XVtseSAtIDFdOwoJfQoJaWYgKGx4ICYmIGx5KSB7CgkJcmVzICs9IHNhW2x4IC0gMV1bbHkgLSAxXTsKCX0KCglyZXR1cm4gcmVzIC8gMjsKfQoKaW50IGRwW05dWzJdOwoKaW50IFNvbHZlKGludCBqLCBpbnQgaSkgewoJaW50IGFucyA9IGogPyBkcFtqIC0gMV1bMF0gOiAwOwoJYW5zICs9IGdldFN1bShqLCBpLCBqLCBpKTsKCXJldHVybiBhbnM7Cn0KCmludCBtYWluKHZvaWQpIHsKCWludCBuLCBrOwoJc2NhbmYoIiVkJWQiLCAmbiwgJmspOwoJUkVQKGksIG4pIHsKCQlSRVAoaiwgbikgewoJCQlzY2FuZigiJWQiLCAmYVtpXVtqXSk7CgkJCXNhW2ldW2pdID0gYVtpXVtqXTsKCQkJaWYgKGkpIHsKCQkJCXNhW2ldW2pdICs9IHNhW2kgLSAxXVtqXTsKCQkJfQoJCQlpZiAoaikgewoJCQkJc2FbaV1bal0gKz0gc2FbaV1baiAtIDFdOwoJCQl9CgkJCWlmIChpICYmIGopIHsKCQkJCXNhW2ldW2pdIC09IHNhW2kgLSAxXVtqIC0gMV07CgkJCX0KCQl9Cgl9CgoJUkVQKGksIG4pIHsKCQlkcFtpXVswXSA9IGdldFN1bSgwLCBpLCAwLCBpKTsKCX0KCglSRVAoaiwgayAtIDEpIHsKCQlkZXF1ZTxpbnQ+cTsKCQlxLnB1c2hfYmFjaygwKTsKCQlkcFswXVsxXSA9IGdldFN1bSgwLCAwLCAwLCAwKTsKCQlGT1IoaSwgMSwgbikgewoJCQl3aGlsZSAoc3oocSkgPj0gMSkgewoJCQkJaW50IGEgPSBTb2x2ZShxLmJhY2soKSwgaSk7CgkJCQlpbnQgYiA9IFNvbHZlKGksIGkpOwoJCQkJaWYgKGEgPD0gYikgewoJCQkJCWJyZWFrOwoJCQkJfQoJCQkJcS5wb3BfYmFjaygpOwoJCQl9CgkJCXEucHVzaF9iYWNrKGkpOwoJCQl3aGlsZSAoc3oocSkgPj0gMikgewoJCQkJaW50IGEgPSBTb2x2ZShxWzBdLCBpKTsKCQkJCWludCBiID0gU29sdmUocVsxXSwgaSk7IAoJCQkJaWYgKGEgPD0gYikgewoJCQkJCWJyZWFrOwoJCQkJfQoJCQkJcS5wb3BfZnJvbnQoKTsKCQkJfQoJCQlkcFtpXVsxXSA9IFNvbHZlKHFbMF0sIGkpOwoJCX0KCQlSRVAoaSwgbikgewoJCQlkcFtpXVswXSA9IGRwW2ldWzFdOwoJCX0KCX0KCglwcmludGYoIiVkXG4iLCBkcFtuIC0gMV1bMF0pOwp9