#include "tickets.h"
#include "bits/stdc++.h"
using namespace std;
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;
for (int i = 0; i < n; i++) {
std::vector<int> row(m);
for (int j = 0; j < m; j++) {
row[j] = -1;
}
answer.push_back(row);
}
vector<int> tries;
for(int i=0; i<n; i++) {
tries.push_back(x[i][0]);
tries.push_back(x[i][m - 1]);
}
sort(tries.begin(), tries.end());
long long ans = -1;
for(long long tt : tries) {
priority_queue<pair<long long, int> > pq;
for(int i=0; i<n; i++) {
pq.push({abs(tt - x[i][0]), i});
pq.push({abs(tt - x[i][m - 1]), n + i});
}
long long smol = 0, big = 0;
int chosen[n];
for(int i=0; i<n; i++) chosen[i] = 0;
long long ss = 0;
while(pq.size()) {
int ff = pq.top().second % n;
int cc = pq.top().second / n;
long long vv = pq.top().first;
pq.pop();
if(chosen[ff]) continue;
long long rr = (cc == 1 ? x[ff][m - 1] : x[ff][0]);
if(rr >= tt && big == n/2) continue;
if(rr < tt && smol == n/2) continue;
chosen[ff] = (cc == 0 ? 1 : 2);
if(cc == 1) big++;
else smol++;
ss += vv;
}
if(ss > ans && big == smol && big == n/2) {
ans = ss;
for(int i=0; i<n; i++) {
for(int j=0; j<m; j++) {
answer[i][j] = -1;
}
}
for(int i=0; i<n; i++) {
if(chosen[i] == 1) answer[i][0] = 0;
else answer[i][m - 1] = 0;
}
}
}
allocate_tickets(answer);
return ans;
}
