#include <bits/stdc++.h>
using namespace std;
using ull = unsigned long long;
#if defined(__GNUC__)
#pragma GCC optimize("Ofast,unroll-loops,inline,fast-math")
#pragma GCC target("sse4.2,avx,avx2,bmi,bmi2,popcnt")
#pragma GCC optimize("no-stack-protector")
#endif
struct Node {
ull st;
int sc;
};
struct Asc {
bool operator()(Node const &a, Node const &b) const {
if (a.sc != b.sc) return a.sc < b.sc;
return a.st < b.st;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int N, K;
long long C;
cin >> N >> K >> C;
static int score[500][6];
for (int i = 0; i < N; i++)
for (int j = 0; j < K; j++)
cin >> score[i][j];
// powers of N for state encoding
vector<ull> powN(K, 1);
for (int i = 1; i < K; i++) powN[i] = powN[i - 1] * (ull)N;
// greedy start‐team
vector<int> start;
start.reserve(K);
vector<char> used(N, 0);
for (int e = 0; e < K; e++) {
int bj = 0, bs = -1;
for (int j = 0; j < N; j++) {
if (!used[j] && score[j][e] > bs) {
bs = score[j][e];
bj = j;
}
}
used[bj] = 1;
start.push_back(bj);
}
sort(start.begin(), start.end());
auto encode = [&](int a[]) {
ull s = 0;
for (int i = 0; i < K; i++) s += powN[i] * (ull)a[i];
return s;
};
auto fullScore = [&](int a[]) {
int tot = 0;
for (int e = 0; e < K; e++) {
int m = 0;
for (int i = 0; i < K; i++)
m = max(m, score[a[i]][e]);
tot += m;
}
return tot;
};
// multiset keeps ascending‐by‐score; largest is *prev(end())
multiset<Node, Asc> pq;
unordered_set<ull> vis;
vis.reserve((size_t)C * K + 10);
// seed
int tmp[6];
for (int i = 0; i < K; i++) tmp[i] = start[i];
pq.insert({encode(tmp), fullScore(tmp)});
vis.insert(pq.begin()->st);
static int cur[6], base[6], baseMax[6], newt[6];
static bitset<500> in;
// pop then expand C−1 times
for (long long iter = 1; iter < C; iter++) {
// 1) take the best
auto itBest = prev(pq.end());
Node top = *itBest;
pq.erase(itBest);
// 2) decode
{
ull x = top.st;
for (int i = 0; i < K; i++) {
cur[i] = int(x % (ull)N);
x /= (ull)N;
}
}
// 3) expand all Hamming‐1 neighbors
for (int rem = 0; rem < K; rem++) {
// build base[0..K-2]
int t = 0;
for (int i = 0; i < K; i++) {
if (i == rem) continue;
base[t++] = cur[i];
}
sort(base, base + (K - 1));
// compute baseMax[e]
for (int e = 0; e < K; e++) baseMax[e] = 0;
for (int i = 0; i < K - 1; i++) {
int x = base[i];
for (int e = 0; e < K; e++)
baseMax[e] = max(baseMax[e], score[x][e]);
}
int bs = accumulate(baseMax, baseMax + K, 0);
// mark used
in.reset();
for (int i = 0; i < K - 1; i++) in.set(base[i]);
// try every j not in that base
size_t limit = C - iter;
for (int j = 0; j < N; j++) {
if (in.test(j)) continue;
int delta = 0;
for (int e = 0; e < K; e++) {
int sje = score[j][e];
if (sje > baseMax[e]) delta += sje - baseMax[e];
}
// merge j into sorted
bool done = false;
int p = 0, q = 0;
while (p < K) {
if (!done && (q == K - 1 || j < base[q])) {
newt[p++] = j;
done = true;
} else {
newt[p++] = base[q++];
}
}
ull nst = 0;
for (int i = 0; i < K; i++) nst += powN[i] * (ull)newt[i];
if (!vis.insert(nst).second) continue;
Node nd{nst, bs + delta};
// bounded‐insert into pq
if (pq.size() < limit) {
pq.insert(nd);
} else {
auto itMin = pq.begin();
if (nd.sc > itMin->sc) {
pq.erase(itMin);
pq.insert(nd);
}
}
}
}
}
// now the top of pq is the C-th best
cout << prev(pq.end())->sc << "\n";
return 0;
}
