#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<int> ptr(n);
priority_queue<pair<int, int>> pq;
for (int i = 0; i < n; i++) pq.push({-x[i][0] - x[i][m - k], i});
long long ret = 0;
int taken = 0;
while (taken < n * k / 2) {
auto [val, i] = pq.top();
pq.pop();
ptr[i]++;
if (ptr[i] < k) pq.push({-x[i][ptr[i]] - x[i][m - k + ptr[i]], i});
taken++;
}
int cur = 0;
vector<int> ending(n);
vector<vector<int>> ans(n, vector<int> (m, -1));
for (int i = 0; i < n; i++) {
for (int j = 0; j < ptr[i]; j++) {
ret -= x[i][j];
ans[i][j] = cur++;
if (cur == k) cur = 0;
}
ending[i] = cur;
}
for (int i = 0; i < n; i++) {
cur = ending[i];
for (int j = 0; j < k - ptr[i]; j++) {
ret += x[i][m - j - 1];
ans[i][m - j - 1] = cur++;
if (cur == k) cur = 0;
}
}
allocate_tickets(ans);
return ret;
}
