#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
int sum[1505], f[1505], b[1505];
vector<vector<int>> ret;
bool cmp(pair<long long, pair<int, int>> a, pair<long long, pair<int, int>> _b)
{
if (a.first != _b.first)
return a.first > _b.first;
else
return a.second < _b.second;
}
long long find_maximum(int k, std::vector<std::vector<int>> d)
{
int c = d.size();
int s = d[0].size();
vector<pair<long long, pair<int, int>>> V;
long long ans = 0;
vector<vector<pair<int, int>>> d2;
d2.resize(c);
for (int i = 0; i < c; i ++)
for (int j = 0; j < s; j ++)
d2[i].push_back({d[i][j], j});
for (int i = 0; i < c; i ++)
{
sort(d2[i].begin(), d2[i].end());
for (int j = 0; j < k; j ++)
V.push_back({(long long)d2[i][s - j - 1].first + d2[i][k - j - 1].first, {i, j}});
for (int j = 0; j < k; j ++)
ans -= d2[i][j].first;
}
sort(V.begin(), V.end(), cmp);
for (int i = 0; i < c * k / 2; i ++)
{
ans += V[i].first;
sum[V[i].second.first] = V[i].second.second + 1;
}
ret.resize(c, vector<int>(s, -1));
for (int i = 0; i < k; i ++)
{
vector<pair<int, int>> v;
for (int j = 0; j < c; j ++)
v.push_back({sum[j], j});
sort(v.begin(), v.end());
for (int j = 0; j < c / 2; j ++)
{
ret[v[j].second][d2[v[j].second][f[v[j].second]].second] = i;
f[v[j].second] ++;
}
for (int j = c / 2; j < c; j++)
{
ret[v[j].second][d2[v[j].second][s - b[v[j].second] - 1].second] = i;
b[v[j].second] ++;
sum[v[j].second] --;
}
}
allocate_tickets(ret);
return ans;
}
/*
static int n_;
static int m_;
static int k_;
static std::vector<std::vector<int>> d_;
static std::vector<std::vector<int>> x_;
static int called_ = 0;
static void check(bool cond, std::string message) {
if (!cond) {
printf("%s\n", message.c_str());
exit(0);
}
}
void allocate_tickets( std::vector<std::vector<int>> _d) {
check(!called_, "allocate_tickets called more than once");
d_ = _d;
check((int)d_.size() == n_, "allocate_tickets called with parameter of wrong size");
for (int i = 0; i < n_; i++) {
check((int)d_[i].size() == m_, "allocate_tickets called with parameter of wrong size");
}
called_ = 1;
}
int main() {
assert(scanf("%d %d %d", &n_, &m_, &k_) == 3);
x_.resize(n_);
for (int i = 0; i < n_; i++) {
x_[i].resize(m_);
for (int j=0; j < m_; j++) {
assert(scanf("%d", &x_[i][j]) == 1);
}
}
fclose(stdin);
long long answer = find_maximum(k_, x_);
check(called_, "failure to call allocate_tickets");
printf("%lld\n", answer);
for (int i = 0; i < n_; i++) {
for (int j = 0; j < m_; j++) {
if (j) printf(" ");
printf("%d", d_[i][j]);
}
printf("\n");
}
fclose(stdout);
return 0;
}
*/
