#include "tickets.h"
#include <vector>
#include <queue>
#include <set>
using namespace std;
#define int long long
long long find_maximum(signed k, std::vector<std::vector<signed>> x) {
int n = x.size();
int m = x[0].size();
std::vector<std::vector<signed>> ans(n, vector<signed>(m, -1));
long long ansv = 0;
priority_queue<pair<int, pair<int, int>>> pq;
set<pair<int, int>> anss, anss2;
for(int j = 0; j < n; j++)
{
for(int i = 0; i < k; i++)
{
ansv += x[j][m-1-i];
anss.insert({m-1-i, -j});
}
pq.push({-x[j][0]-x[j][m-k], {j, 0}});
}
int ac = k*n/2;
while(ac--)
{
auto ss = pq.top();
pq.pop();
anss2.insert({ss.second.second, ss.second.first});
anss.erase({m-k+ss.second.second, -ss.second.first});
ansv += ss.first;
if(ss.second.second < k-1)
pq.push({-x[ss.second.first][ss.second.second+1]-x[ss.second.first][m-k+(ss.second.second+1)], {ss.second.first, ss.second.second+1}});
}
int tim = 0;
for(auto vv : anss)
{
ans[-vv.second][vv.first] = tim/(n/2);
tim++;
}
tim = 0;
for(auto vv : anss2)
{
ans[vv.second][vv.first] = tim/(n/2);
tim++;
}
allocate_tickets(ans);
return ansv;
}
