#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
void allocate_tickets(std::vector <std::vector <int>> s);
int n, m;
ull find_maximum(int k, std::vector <std::vector <int>> x) {
n = x.size();
m = x[0].size();
ll r = 0;
for (int i = 0; i < n; i++)
for (int j = m - 1; j > m - 1 - k; j--)
r += x[i][j];
std::vector <std::pair <int, int>> range(n, { -1, m - k });
std::priority_queue <std::pair <int, int>> pq;
for (int i = 0; i < n; i++)
pq.push({ - x[i][range[i].first + 1] - x[i][range[i].second], i });
for (int i = 0; i < (n * k) >> 1; i++) {
auto p = pq.top(); pq.pop();
r += p.first;
range[p.second].first++, range[p.second].second++;
if (range[p.second].second == m) continue;
pq.push({ - x[p.second][range[p.second].first + 1] - x[p.second][range[p.second].second], p.second });
}
std::vector <std::vector <int>> mx(n), mn(n), mxi(n), mni(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j <= range[i].first; j++)
mn[i].push_back(x[i][j]), mni[i].push_back(j);
for (int j = range[i].second; j < m; j++)
mx[i].push_back(x[i][j]), mxi[i].push_back(j);;
std::reverse(mn[i].begin(), mn[i].end());
std::reverse(mni[i].begin(), mni[i].end());
}
std::vector <std::vector <int>> ans(n, std::vector <int> (m, -1));
for (int i = 0; i < k; i++) {
int hasmn = 0;
std::vector <int> mnmx(n, 0);
std::priority_queue <std::pair <int, int>> pqq;
for (int j = 0; j < n; j++) {
if (mx[j].size()) {
mnmx[j] = 1;
if (mn[j].size()) {
pqq.push({ - mn[j].back() - mx[j].back(), j });
}
} else {
mnmx[j] = -1;
hasmn++;
}
}
while (hasmn < (n >> 1)) {
auto p = pqq.top(); pqq.pop();
mnmx[p.second] = -1;
hasmn++;
}
for (int j = 0; j < n; j++) {
if (mnmx[j] == 1) {
ans[j][mxi[j].back()] = i;
mx[j].pop_back();
mxi[j].pop_back();
} else {
ans[j][mni[j].back()] = i;
mn[j].pop_back();
mni[j].pop_back();
}
}
}
allocate_tickets(ans);
return r;
}
