#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for(int i{}; i < (n); ++i)
long long find_maximum(int k, vector<vector<int>> x) {
int n = x.size(), m = x[0].size();
long long ans{};
rep(i, n) rep(j, k)
ans -= x[i][j];
vector<int> max_unused(n, m - 1), max_small(n, k - 1);
priority_queue<pair<int, int>> p;
rep(i, n)
p.push({x[i][max_unused[i]] + x[i][max_small[i]], i});
rep(_, n * k / 2) {
auto [d, i] = p.top(); p.pop();
ans += d;
--max_unused[i], --max_small[i];
if(max_small[i] >= 0)
p.push({x[i][max_unused[i]] + x[i][max_small[i]], i});
}
vector<vector<int>> allocation(n, vector<int>(m, -1));
vector<int> order(n); iota(order.begin(), order.end(), 0);
rep(r, k) {
sort(order.begin(), order.end(), [&](int i, int j) {
return max_unused[i] < max_unused[j];
});
rep(i, n)
if(i >= n / 2) {
assert(max_small[order[i]] >= 0);
allocation[order[i]][max_small[order[i]]] = r;
max_small[order[i]]--;
} else {
assert(max_unused[order[i]] < m - 1);
allocation[order[i]][max_unused[order[i]] + 1] = r;
max_unused[order[i]]++;
}
}
allocate_tickets(allocation);
return ans;
}
