#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
long long find_maximum(int k, vector<vector<int>> x) {
int n = x.size();
int m = x[0].size();
vector<vector<pair<ll, int>>> a(n, vector<pair<ll, int>>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) a[i][j] = {x[i][j], j};
}
ll ans = 0;
vector<pair<int, int>> v(n);
vector<int> s_cnt(n);
priority_queue<pair<ll, int>> pq;
for (int i = 0; i < n; i++) {
v[i] = {k-1, m-1};
pq.push({x[i][k-1]+x[i][m-1], i});
for (int j = 0; j < k; j++) {
ans -= x[i][j];
s_cnt[i]++;
}
}
int l = 0;
int targ = n/2*k;
while (l < targ) {
auto [add, i] = pq.top();
pq.pop();
ans += add;
s_cnt[i]--;
l++;
swap(a[i][v[i].first], a[i][v[i].second]);
v[i].first--, v[i].second--;
if (v[i].second < k) v[i].second = m-1;
if (v[i].first >= 0) pq.push({a[i][v[i].first].first+a[i][v[i].second].first, i});
}
vector<vector<pair<int, int>>> rounds(k);
vector<int> small(k), large(k);
vector<int> ptr(n);
for (int i = 0; i < n; i++) {
vector<bool> done(k);
for (int j = 0; j < k && ptr[i] < s_cnt[i]; j++) {
if (!done[j] && small[j] < n/2) {
done[j] = true;
small[j]++;
rounds[j].push_back({i, a[i][ptr[i]].second});
ptr[i]++;
}
}
for (int j = 0; j < k; j++) {
if (!done[j] && large[j] < n/2) {
done[j] = true;
large[j]++;
rounds[j].push_back({i, a[i][ptr[i]].second});
ptr[i]++;
}
}
}
vector<vector<int>> answer(n, vector<int>(m, -1));
for (int i = 0; i < k; i++) {
for (int j = 0; j < n; j++) {
answer[rounds[i][j].first][rounds[i][j].second] = i;
}
}
allocate_tickets(answer);
return ans;
}
