# 2. 题解

#include <bits/stdc++.h>

#define NS (20)

using namespace std;

template<typename _Tp> inline void IN(_Tp& dig)
{
char c; bool flag = 0; dig = 0;
while (c = getchar(), !isdigit(c)) if (c == '-') flag = 1;
while (isdigit(c)) dig = dig * 10 + c - '0', c = getchar();
if (flag) dig = -dig;
}

int n, k, d[NS][NS], lim;

bool book[NS];

bool Chk(int rem)
{
int sum[NS][NS], cnt = 1, tot[NS];
memset(sum, 0, sizeof(sum)), memset(tot, 0, sizeof(tot));
for (int i = 1; i <= n; i += 1)
{
for (int j = 1; j <= n; j += 1) sum[cnt][j] += d[i][j];
if (book[i]) cnt++;
}
for (int i = 1; i <= n; i += 1)
{
int mx = 0;
for (int j = 1; j <= cnt; j += 1)
{
if (sum[j][i] > lim) return 0;
tot[j] += sum[j][i], mx = max(mx, tot[j]);
}
if (mx > lim)
{
if (!rem) return 0;
rem--;
for (int j = 1; j <= cnt; j += 1)
tot[j] = sum[j][i];
}
}
return 1;
}

bool Jud(int a, int rem)
{
if (a >= n) return Chk(rem);
if (rem)
{
book[a] = 1;
if (Jud(a + 1, rem - 1)) return 1;
}
book[a] = 0;
if (Jud(a + 1, rem)) return 1;
return 0;
}

int main(int argc, char const* argv[])
{
IN(n), IN(k);
int l = 0, r = 0;
for (int i = 1; i <= n; i += 1)
for (int j = 1; j <= n; j += 1)
IN(d[i][j]), l = max(l, d[i][j]), r += d[i][j];
while (l < r)
{
lim = (l + r) >> 1;
if (Jud(1, k)) r = lim;
else l = lim + 1;
}
printf("%d\n", l);
return 0;
}