#include <bits/stdc++.h>
#include <cstdio>
#pragma GCC optimize("O3")
#define endl '\n'
using namespace std;
void allocate_tickets(vector <vector <int> > r);
long long find_maximum(int k, vector <vector <int> > x) {
int n = (int)x.size(), m = (int)x[0].size();
vector <int> taken(n, k);
long long ans = 0;
int balance = 0;
priority_queue <pair <int, int> > pq;
for (int i = 0; i < n; i++) {
for (int j = m - k; j < m; j++)
ans += x[i][j];
taken[i] = k;
balance += k;
pq.push({-x[i][m-k]-x[i][0], i});
}
while (balance > 0) {
pair <int, int> curr = pq.top();
pq.pop();
ans += curr.first;
balance -= 2;
taken[curr.second]--;
if (taken[curr.second] != 0)
pq.push({-x[curr.second][m-taken[curr.second]]-x[curr.second][k-taken[curr.second]], curr.second});
}
vector <pair <int, pair <int, int> > > vec;
for (int i = 0; i < n; i++) {
for (int j = 0; j < k - taken[i]; j++)
vec.push_back({x[i][j], {-i-1, j}});
for (int j = m - taken[i]; j < m; j++)
vec.push_back({x[i][j], {i, j}});
}
sort (vec.begin(), vec.end());
set <pair <int, int> > s;
vector <vector <int> > r(n, vector <int> (m, -1));
vector <vector <bool> > used(k, vector <bool> (n, false));
for (int i = 0; i < k; i++)
s.insert({0, i});
vector <int> cnt0(k, 0);
vector <int> maxs(k, 0);
for (auto i: vec)
if (i.second.first < 0) {
for (auto it = prev(s.end()); ; it--) {
if (!used[it->second][-i.second.first-1] && cnt0[it->second] < n / 2) {
cnt0[it->second]++;
maxs[it->second] = max(maxs[it->second], i.first);
used[it->second][-i.second.first-1] = true;
r[-i.second.first-1][i.second.second] = it->second;
auto to_insert = *it;
to_insert.first--;
s.erase(it);
s.insert(to_insert);
break;
}
}
}
vector <pair <int, int> > v;
for (int i = 0; i < k; i++)
v.push_back({maxs[i], i});
sort (v.begin(), v.end());
reverse(v.begin(), v.end());
vector <int> cnt1(k, 0);
for (auto i: vec)
if (i.second.first >= 0) {
for (auto j: v)
if (i.first >= j.first && !used[j.second][i.second.first] && cnt1[j.second] < n / 2) {
cnt1[j.second]++;
used[j.second][i.second.first] = true;
r[i.second.first][i.second.second] = j.second;
break;
}
}
allocate_tickets(r);
/*
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++)
cout << r[i][j] << " ";
cout << endl;
}
*/
return ans;
}
/*
int n, m, k;
int main() {
cin >> n >> m >> k;
vector <vector <int> > x(n, vector <int> (m));
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
cin >> x[i][j];
cout << find_maximum(k, x) << endl;
}
*/
