#include "tickets.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define int long long
int find_maximum(signed k, std::vector<std::vector<signed>> x) {
int colors = x.size();
int ticketsPerColor = x[0].size();
priority_queue<array<int, 4>> pq; // val, col, indO, indN;
int res = 0;
for (int i=0; i<colors; i++) {
for (int j = 0; j<k; j++) {
res -= x[i][j];
pq.push({x[i][j] + x[i][ticketsPerColor-(k-j)], i, j, ticketsPerColor-(k-j)});
}
}
vector<pair<int, int>> numused(colors);
for (int i = 0; i<colors; i++) numused[i].second = i;
for (int i = 0; i<colors*k/2; i++) {
res += pq.top()[0];
numused[pq.top()[1]].first++;
// used[pq.top()[1]][pq.top()[2]] = 0;
// used[pq.top()[1]][pq.top()[3]] = 2;
pq.pop();
}
sort(numused.rbegin(), numused.rend());
// for (auto i:numused) cerr << i.first << " ";
// cerr << "\n";
vector<pair<int, int>> bounds(colors, {0, ticketsPerColor-1});
vector<vector<signed>> ass(colors, vector<signed>(ticketsPerColor, -1));
for (int i = 0; i<k; i++) {
int used = 0;
for (int j = 0; j<colors; j++) {
// cerr << used << " ";
if (used >= colors/2) {
ass[numused[j].second][bounds[j].first] = i;
bounds[j].first++;
} else {
if (ticketsPerColor-1-bounds[j].second < numused[j].first) {
ass[numused[j].second][bounds[j].second] = i;
bounds[j].second--;
used++;
}
else {
ass[numused[j].second][bounds[j].first] = i;
bounds[j].first++;
}
}
}
assert(used == colors/2);
// cerr << "\n";
}
allocate_tickets(ass);
return res;
}
