#include "tickets.h"
#include <vector>
#include <numeric>
#include <algorithm>
using ll = long long;
long long find_maximum(int K, std::vector<std::vector<int>> x) {
int N = x.size();
int M = x[0].size();
std::vector<std::vector<int>> answer(N, std::vector<int>(M, -1));
ll ans=0;
std::vector<int> L(N, 0), R(N, M);
std::vector<int> ord(N), gain(N);
std::iota(ord.begin(), ord.end(), 0);
for(int i=0;i<K;++i)
{
for(int j=0;j<N;++j)
gain[j]=x[j][L[j]]+x[j][R[j]-1];
std::nth_element(ord.begin(), ord.begin()+N/2, ord.end(), [&](int u, int v){return gain[u]<gain[v];});
for(int j=0;j<N/2;++j)
answer[ord[j]][L[ord[j]]]=i, ans -= x[ord[j]][L[ord[j]]], ++L[ord[j]];
for(int j=N/2;j<N;++j)
--R[ord[j]], answer[ord[j]][R[ord[j]]]=i, ans += x[ord[j]][R[ord[j]]];
}
allocate_tickets(answer);
return ans;
}
