#include "tickets.h"
#include <vector>
#include <algorithm>
#include <numeric>
#include <cassert>
#define int long long
using namespace std;
long long find_maximum(signed k, vector<vector<signed>> x) {
int n = x.size();
int m = x[0].size();
vector<vector<signed>> answer (n, vector<signed> (m, -1));
vector<int> alls;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < m; ++j) {
alls.push_back(x[i][j]);
}
}
nth_element(alls.begin(), alls.begin() + n/2 * m, alls.end());
int globalmedian = alls[n/2*m];
int ans = 0;
vector<pair<int, int>> tb (n, {0, m-1});
for (int i = 0; i < k; ++i) {
vector<int> bgains (n);
for (int j = 0; j < n; ++j) {
int top = x[j][tb[j].second] - globalmedian;
int bottom = globalmedian - x[j][tb[j].first];
bgains[j] = bottom - top;
}
vector<int> inds (n);
iota(inds.begin(), inds.end(), 0);
nth_element(inds.begin(), inds.begin() + n/2, inds.end(), [&](int a, int b){return bgains[a] > bgains[b];});
for (int bottom = 0; bottom < n/2; ++bottom) {
//assert(x[inds[bottom]][tb[inds[bottom]].first] <= globalmedian);
ans += abs(globalmedian - x[inds[bottom]][tb[inds[bottom]].first]);
answer[inds[bottom]][tb[inds[bottom]].first] = i;
tb[inds[bottom]].first++;
}
for (int top = n/2; top < n; ++top) {
//assert(x[inds[top]][tb[inds[top]].second] >= globalmedian);
ans += abs(x[inds[top]][tb[inds[top]].second] - globalmedian);
answer[inds[top]][tb[inds[top]].second] = i;
tb[inds[top]].second--;
}
}
allocate_tickets(answer);
return ans;
}
