#include <bits/stdc++.h>
#include "tickets.h"
using ll = long long;
template <class T> using Vec = std::vector<T>;
ll find_maximum(int K, Vec<Vec<int>> X) {
const int N = (int) X.size();
const int M = (int) X[0].size();
ll ret = 0;
std::priority_queue<std::pair<int, int>> heap;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < K; ++j) {
ret -= X[i][j];
heap.emplace(X[i][M - j - 1] + X[i][K - j - 1], i);
}
}
Vec<int> up(N);
for (int i = 0; i < N * K / 2; ++i) {
const auto [a, k] = heap.top();
heap.pop();
ret += a;
up[k] += 1;
}
Vec<Vec<int>> Y(N, Vec<int>(M, -1));
int s = 0, t = K;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < K - up[i]; ++j) {
Y[i][j] = s;
s += 1;
if (s == K) {
s = 0;
}
}
for (int j = 0; j < up[i]; ++j) {
t -= 1;
Y[i][M - j - 1] = t;
if (t == 0) {
t = K;
}
}
}
allocate_tickets(Y);
return ret;
}
