#include "bits/stdc++.h"
#include "tickets.h"
using namespace std;
long long find_maximum(int k, vector<vector<int>> x) {
int n = x.size();
int m = x[0].size();
assert(m == k);
vector <array <int ,3>> all; //{val ,color ,index}
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
all.push_back({x[i][j] ,i ,j});
sort(all.begin() ,all.end());
vector <array <int ,3>> fh{all.begin() ,all.begin() + (int)all.size()/2};
vector <array <int ,3>> sh{all.begin() + (int)all.size()/2 ,all.end()};
sort(fh.begin() ,fh.end() ,[](auto&i ,auto&j){ return i[1] < j[1]; });
sort(sh.begin() ,sh.end() ,[](auto&i ,auto&j){ return i[1] < j[1]; });
int64_t tot = 0;
vector<vector<int>> answer(n ,vector<int>(m ,-1));
set <int> mex[n];
for(int i = 0; i < k; i++)
for(int c = 0; c < n; c++)
mex[c].insert(i);
int round_number = 0;
for(auto&c : fh){
tot -= c[0];
answer[c[1]][c[2]] = round_number;
mex[c[1]].erase(answer[c[1]][c[2]]);
//cout << "(" << c[1] << " ," << c[2] << ") -> " << answer[c[1]][c[2]] << endl;
round_number = (round_number+1)%k;
}
for(auto&c : sh){
tot += c[0];
answer[c[1]][c[2]] = *mex[c[1]].begin();
//cout << "(" << c[1] << " ," << c[2] << ") -> " << answer[c[1]][c[2]] << endl;
mex[c[1]].erase(answer[c[1]][c[2]]);
}
allocate_tickets(answer);
return tot;
}
