#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<pair<int, int>> vpii;
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
vpii.emplace_back(i, j);
queue<int> qi;
map<int, int> mii;
for (int i = 0; i < k; i++) {
mii[i] = n / 2;
for (int j = 0; j < n / 2; j++)
qi.push(i);
}
vector<vector<int>> answer(n, vector<int>(m, -1));
sort(vpii.begin(), vpii.end(), [&](pair<int, int> a, pair<int, int> b) {
return x[a.first][a.second] > x[b.first][b.second];
});
vector<set<int>> vsi(n);
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++)
vsi[i].insert(j);
long long tot = 0;
for (int i = 0; i < vpii.size(); i++) {
auto [a, b] = vpii[i];
auto it = mii.lower_bound(m - b - 1);
if (it == mii.end()) {
tot -= x[a][b];
} else {
tot += x[a][b];
answer[a][b] = it->first;
vsi[a].erase(it->first);
it->second--;
if (it->second == 0)
mii.erase(it);
}
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if (answer[i][j] == -1) {
answer[i][j] = *vsi[i].begin();
vsi[i].erase(vsi[i].begin());
}
}
}
allocate_tickets(answer);
return tot;
}
