#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();
long long res = 0;
vector<int> id(n, k - 1);
priority_queue<pair<int, int>> pq;
for (int i = 0; i < n; ++i) {
pq.push(make_pair(x[i][k - 1] + x[i][m - 1], i));
for (int j = 0; j < k; ++j) {
res -= x[i][j];
}
}
for (int i = 0; i < n * k / 2; ++i) {
auto [s, y] = pq.top();
pq.pop();
res += s;
--id[y];
if (id[y] >= 0) {
pq.push(make_pair(x[y][id[y]] + x[y][m - (k - id[y])], y));
}
}
vector<array<int, 3>> cand;
for (int i = 0; i < n; ++i) {
cand.push_back({id[i], m - (k - id[i]) + 1, i});
}
vector<vector<int>> opt(n, vector<int>(m, -1));
for (int j = 0; j < k; ++j) {
sort(cand.begin(), cand.end());
for (int i = 0; i < n; ++i) {
int cur = 0;
if (i < n / 2) {
cur = (cand[i][1]++);
} else {
cur = (cand[i][0]--);
}
opt[cand[i][2]][cur] = j;
}
}
allocate_tickets(opt);
return res;
}
