#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 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;
//cerr<<l[i] << ' ' << r[i] << endl;
pq.push({x[i][l[i]]-1e9+x[i][r[i]],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]&&x[i][r[i]]>=0){
pq.push({x[i][l[i]]-1e9+x[i][r[i]],i});
}
}
int vmin = 1e9,vmax = 0;
for(int i=0;i<n;i++){
//cerr<<l[i] << ' ' << r[i] << endl;
for(int j=0;j<l[i];j++){
vmin=min(vmin,x[i][j]);
}
for(int j=m-1;j>r[i];j--){
vmax=max(vmax,x[i][j]);
}
}
long long ans = (long long)(vmax-vmin)*((long long)n*k/2);
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-=x[i][j]-vmin;
low[i].push_back(j);
}
for(int j=m-1;j>r[i];j--){
ans-=vmax-x[i][j];
high[i].push_back(j);
}
}
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;
}
