#include <bits/stdc++.h>
#include "tickets.h"
// #include "grader.cpp"
using namespace std;
typedef long long ll;
ll find_maximum(int k, vector<vector<int>> x) {
int n = x.size();
int m = x[0].size();
vector<vector<int>> output;
output.resize(n);
for (int i = 0; i < n; i ++)
output[i].resize(m, -1);
ll res = 0;
int mn[n], mx[n], mxp[n];
priority_queue<pair<int, int>> pq;
for (int i = 0; i < n; i ++){
for (int j = 0; j < k; j ++)
res -= x[i][j];
mn[i] = k, mx[i] = mxp[i] = 0;
pq.push({x[i][m - mx[i] - 1] + x[i][mn[i] - 1], i});
}
int flips = (n / 2) * k;
while (flips--){
auto [inc, col] = (pq.top());
pq.pop();
res += inc;
mn[col]--;
mx[col]++;
if (mn[col])
pq.push({x[col][m - mx[col] - 1] + x[col][mn[col] - 1], col});
}
for (int round = 0; round < k; round ++){
vector<int> mins, maxs;
while (!pq.empty()) pq.pop();
for (int i = 0; i < n; i ++){
if (mx[i] == 0) mins.push_back(i);
else if (mn[i] == 0) maxs.push_back(i);
else pq.push({x[i][mn[i] - 1], i});
}
while (mins.size() < n / 2){
mins.push_back((pq.top()).second);
pq.pop();
}
while (pq.size()){
maxs.push_back((pq.top()).second);
pq.pop();
}
for (int i : mins){
output[i][mn[i] - 1] = round;
mn[i]--;
}
for (int i : maxs){
output[i][m - mxp[i] - 1] = round;
mxp[i]++;
mx[i]--;
}
}
allocate_tickets(output);
return res;
}
