#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define fast ios_base::sync_with_stdio(false), cin.tie(nullptr), cout.tie(nullptr);
#define MOD 1000000007
#define inf 1e18
#define fi first
#define se second
#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(a) ((int)(a).size())
#define endl '\n'
#define pi 3.14159265359
#define TASKNAME "olympiad"
using namespace std;
template<typename T> bool maximize(T &res, const T &val) { if (res < val){ res = val; return true; }; return false; }
template<typename T> bool minimize(T &res, const T &val) { if (res > val){ res = val; return true; }; return false; }
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
typedef vector<int> vi;
const int MAXN = 5e5 + 9;
int n, k, c;
int a[MAXN][7];
namespace subtask1{
bool check(){
return n <= 500 and k <= 2 and c <= 2000;
}
vector<int> listVal;
void solve(){
FOR(i, 1, n){
FOR(j, i + 1, n){
int p = 0;
FOR(t, 1, k){
p += max(a[i][t], a[j][t]);
}
listVal.pb(p);
}
}
sort(listVal.rbegin(), listVal.rend());
cout << listVal[c - 1] << ' ';
}
}
namespace subtask2{
bool check(){
return n <= 40 or (n <= 500 and k <= 2);
}
int cnt[6000009];
vector<int> curTeam, listVal, sortedListVal;
int getScore(){
int ans = 0;
FOR(i, 1, k){
int cur = 0;
FOR(j, 0, (int) curTeam.size() - 1){
maximize(cur, a[curTeam[j]][i]);
}
ans += cur;
}
return ans;
}
void backtrack(int pos){
if (curTeam.size() == k){
listVal.pb(getScore());
return;
}
if (pos == n + 1){
return;
}
backtrack(pos + 1);
curTeam.pb(pos);
backtrack(pos + 1);
curTeam.pop_back();
}
void solve(){
backtrack(1);
sortedListVal.resize(listVal.size() + 9);
FOR(i, 0, (int) listVal.size() - 1){
cnt[listVal[i]]++;
}
FORD(i, 6000000, 0){
cnt[i] += cnt[i + 1];
}
FOR(i, 0, (int) listVal.size() - 1){
sortedListVal[--cnt[listVal[i]]] = listVal[i];
}
cout << sortedListVal[c - 1] << endl;
}
}
namespace subtask4{
bool check(){
return true;
}
/**
Fracturing search:
Vỡi mỗi cách chọn, mình sẽ chọn thằng
- B1: thằng lớn nhất trong số các thằng chưa được chọn ở sự kiện 1
- ... Bk: tương tự.
Bây giờ, mình sẽ chia không gian tìm kiếm thành các vùng:
- ban thằng 1 đi,
- dùng thằng 1, nhưng ban thằng 2 đi.
- dùng thằng 1, 2 nhưng ban thằng 3 đi.
**/
struct Node{
int score = 0;
vector<int> forbidden;
vector<int> forced;
vector<int> best;
Node(){
score = 0;
forbidden.resize(n + 1, 0);
// cerr << "WHY" << endl;
}
Node(int _score, vector<int> _forbidden, vector<int> _forced, vector<int> _best){
score = _score;
forbidden = _forbidden;
forced = _forced;
best = _best;
}
bool operator < (const Node &other) const {
return score < other.score;
}
};
Node evaluate(vector<int> &forced, vector<int> &forbidden){
vector<int> best;
FOR(i, 0, (int) forced.size() - 1){
best.pb(forced[i]);
}
FOR(i, forced.size(), k - 1){
best.pb(-1);
FOR(j, 1, n){
bool ch = true;
for(auto x: best) if (x == j) ch = false;
if (!forbidden[j] and ch) {
if (best[i] == -1 or a[best[i]][i + 1] < a[j][i + 1]){
best[i] = j;
}
}
}
}
int new_score = 0;
// for(auto x: best){
// cerr << x << ' ';
// }
// cerr << endl;
FOR(i, 0, k - 1){
int mx = 0;
FOR(j, 0, k - 1){
if (best[j] == -1) continue;
maximize(mx, a[best[j]][i + 1]);
}
new_score += mx;
}
return Node(new_score, forbidden, forced, best);
}
priority_queue<Node, vector<Node>> pq;
vector<int> result;
void solve(){
Node start;
start = evaluate(start.forced, start.forbidden);
pq.push(start);
while(result.size() < c){
int cur_score = pq.top().score;
vector<int> best = pq.top().best;
vector<int> new_forced = pq.top().forced;
vector<int> new_forbidden = pq.top().forbidden;
result.pb(cur_score);
pq.pop();
for(int i = new_forced.size(); i < k; i++){
new_forbidden[best[i]] = 1;
Node nw = evaluate(new_forced, new_forbidden);
int new_score = nw.score;
bool valid = true;
FOR(j, 0, k - 1){
if (nw.best[j] == -1) valid = false;
}
if (valid) pq.push(nw);
new_forced.pb(best[i]);
}
}
// for(auto x: result){
// cout << x << ' ';
// }
// cout << endl;
cout << result[c - 1] << endl;
}
}
main()
{
fast;
if (fopen(TASKNAME".inp","r")){
freopen(TASKNAME".inp","r",stdin);
freopen(TASKNAME".out","w",stdout);
}
cin>> n>> k >> c;
FOR(i, 1, n){
FOR(j, 1, k){
cin >> a[i][j];
}
}
// if (subtask1::check()) return subtask1::solve(), 0;
if (subtask2::check()) return subtask2::solve(), 0;
if (subtask4::check()) return subtask4::solve(), 0;
}
/**
Warning:
Đọc sai đề???
Cận lmao
Code imple thiếu case nào không.
Limit.
5 4 4
7 0 4 9
3 0 8 4
1 1 3 7
5 1 3 4
4 2 2 9
**/
