#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
long long find_maximum(int k, vector<vector<int>> x) {
int n = (int) x.size();
int m = (int) x[0].size();
// choose k items for each color
// choose a total of nk/2 + and nk/2 -
// maximize the sum of + and -
long long ans = 0;
vector<int> negative(n, k);
vector<int> positive(n, 0);
for (int i = 0; i < n; i++) {
for (int j = 0; j < k; j++) {
ans -= x[i][j];
}
}
priority_queue<pair<int, int>> pq;
for (int i = 0; i < n; i++) {
if (negative[i] > 0) {
pq.emplace(x[i][m - positive[i] - 1] + x[i][negative[i] - 1], i);
}
}
for (int rep = 0; rep < n * k / 2 && !pq.empty(); rep++) {
int i = pq.top().second;
ans += pq.top().first;
pq.pop();
negative[i]--;
positive[i]++;
if (negative[i] > 0) {
pq.emplace(x[i][m - positive[i] - 1] + x[i][negative[i] - 1], i);
}
}
vector<pair<int, int>> small;
vector<pair<int, int>> large;
for (int i = 0; i < n; i++) {
for (int j = 0; j < negative[i]; j++) {
small.emplace_back(i, j);
}
for (int j = 0; j < positive[i]; j++) {
large.emplace_back(i, m - j - 1);
}
}
sort(begin(small), end(small));
sort(begin(large), end(large));
vector<vector<pair<int, int>>> rounds(k);
vector<vector<int>> inround(k, vector<int>(n, 0));
for (int i = 0; i < n * k / 2; i++) {
rounds[i % k].emplace_back(small[i]);
inround[i % k][small[i].first] = 1;
}
for (int i = 0, j; i < n * k / 2; i = j + 1) {
for (j = i; j + 1 < n * k / 2 && large[i].first == large[j + 1].first; j++);
vector<pair<int, int>> elems;
for (int e = i; e <= j; e++) {
elems.emplace_back(large[e]);
}
for (int r = 0; r < k; r++) {
if (inround[r][large[i].first] == 0) {
inround[r][large[i].first] = 1;
rounds[r].emplace_back(elems.back());
elems.pop_back();
}
}
}
vector<vector<int>> tickets(n, vector<int>(m, -1));
for (int r = 0; r < k; r++) {
for (int i = 0; i < n; i++) {
tickets[rounds[r][i].first][rounds[r][i].second] = r;
}
}
allocate_tickets(tickets);
return ans;
}
