#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
long long find_maximum(int k, vector<vector<int>> x) {
int n = x.size();
int m = x[0].size();
vector<vector<int>> answer(n, vector<int>(m));
vector<vector<bool>> mark(n, vector<bool>(k));
vector<pair<long long, int>> val;
vector<int> big(n, k), small(n, 0);
long long sum = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < k; j++) {
sum += x[i][j + m - k];
val.emplace_back(x[i][j + m - k] + x[i][j], i);
}
}
sort(val.begin(), val.end(), greater<>());
for (int i = 0; i < ((n * k) >> 1); i++) {
sum -= val[i].first;
big[val[i].second]--;
small[val[i].second]++;
}
int gr = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < small[i]; j++) {
mark[i][answer[i][j] = gr] = 1;
gr++;
if (gr >= k) gr = 0;
}
}
for (int i = 0; i < n; i++) {
gr = 0;
for (int j = m - big[i]; j < m; j++) {
while (mark[i][gr]) gr++;
answer[i][j] = gr++;
}
}
allocate_tickets(answer);
return sum;
}
