#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();
int all_x[n*m];
for (int i = 0; i < n; i++) {
for(int j=0;j<m;j++){
all_x[i*m+j] = x[i][j];
}
}
nth_element(all_x,all_x+n*m/2,all_x+n*m);
int med = all_x[n*m/2];
for (int i = 0; i < n; i++) {
for(int j=0;j<m;j++){
x[i][j] -= med;
//printf("%d ",x[i][j]);
}//puts("");
}
int l[n],r[n];
int neg = 0;
priority_queue<pair<int,int> >pq;
for(int i=0;i<n;i++){
l[i]=k;r[i]=m-1;
for(int j=0;j<k;j++){
if(x[i][j]>0){
l[i]=j;r[i]=m-1-(k-j);
break;
}
}
//cerr<<l[i] << ' ' << r[i] << endl;
if(l[i]<=r[i]&&l[i]&&x[i][r[i]]>=0){
pq.push({x[i][r[i]]+abs(x[i][l[i]-1]),i});
}
neg+=l[i];
}
while(neg>n*k/2){
assert(pq.size());
pair<int,int> ctop = pq.top();pq.pop();
int i= ctop.second;
neg--;
l[i]--;r[i]--;
if(l[i]<=r[i]&&l[i]&&x[i][r[i]]>=0){
pq.push({x[i][r[i]]+abs(x[i][l[i]-1]),i});
}
}
long long ans = 0;
vector<int> low[n], high[n];
for(int i=0;i<n;i++){
//cerr<<l[i] << ' ' << r[i] << endl;
for(int j=0;j<l[i];j++){
ans+=abs(x[i][j]);
low[i].push_back(j);
assert(x[i][j]<=0);
}
for(int j=m-1;j>r[i];j--){
ans+=abs(x[i][j]);
high[i].push_back(j);
assert(x[i][j]>=0);
}
}
std::vector<std::vector<int>> answer(n,vector<int>(m,-1));
pair<int,int> diff2id[n];
/*for(int i=0;i<n;i++){
printf("%d %d\n",storel[i],storer[i]);
printf("lo: ");
for(int j:low[i])printf("%d ",j);
printf("high: ");
for(int j:high[i])printf("%d ",j);
puts("");
}*/
for(int r=0;r<k;r++){
for(int i=0;i<n;i++)diff2id[i] = make_pair(high[i].size()-low[i].size(),i);
sort(diff2id,diff2id+n);
for(int i=0;i<n;i++){
if(i<n/2){
int x = diff2id[i].second;
answer[x][low[x].back()] = r;
low[x].pop_back();
}
else{
int x = diff2id[i].second;
answer[x][high[x].back()] = r;
high[x].pop_back();
}
}
}
allocate_tickets(answer);
return ans;
}
