#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];
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] = 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});
}
int round = 0;
for (int i = 0; i < n; i ++){
for (int j = 0; j < mn[i]; j ++, round = (round + 1) % k)
output[i][j] = round;
for (int j = m - mx[i]; j < m; j ++, round = (round + 1) % k)
output[i][j] = round;
}
allocate_tickets(output);
return res;
}
