#include "tickets.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
using idata = vector<int>;
using igrid = vector<idata>;
using di = pair<int, int>;
using vd = vector<di>;
int find_maximum(signed K, vector<vector<signed>> x) {
assert(K == 1);
int N = x.size(); int M = x[0].size(); int H = N >> 1;
idata minv(N, 1e16), maxv(N, -1e16);
for (int i = 0; i < N; i ++) {
for (int u : x[i]) {
minv[i] = min(minv[i], u);
maxv[i] = max(maxv[i], u);
}
}
int result = -1; idata ub;
for (int mid = 0; mid < N; mid ++) {
int locr = 0;
idata used_bot = { mid };
vd values;
for (int i = 0; i < N; i ++) {
if (i == mid) continue ;
values.push_back({
minv[i] > minv[mid] ? - 1e15 : minv[mid] - minv[i],
maxv[i] < minv[mid] ? - 1e15 : maxv[i] - minv[mid]
});
}
vd comp;
int i = 0;
for (const auto v : values) {
if (i == mid) i ++;
locr += v.second;
comp.push_back({ v.first - v.second, i });
i ++;
}
sort(comp.rbegin(), comp.rend());
for (int i = 0; i + 1 < H; i ++) {
locr += comp[i].first;
used_bot.push_back(comp[i].second);
}
if (locr <= result) continue ;
result = locr;
ub.swap(used_bot);
}
vector<vector<signed>> allocations(N, vector<signed>(M, -1));
vector<bool> used_bot(N, false);
for (int u : ub) used_bot[u] = true;
for (int i = 0; i < N; i ++) {
int target = used_bot[i] ? minv[i] : maxv[i];
for (int j = 0; j < M; j ++) {
if (x[i][j] != target) continue ;
allocations[i][j] = 0;
break ;
}
}
allocate_tickets(allocations);
return result;
}
