#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
using lint=long long;
using pii=pair<int,int>;
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++){
answer.pb(vector<int>(m,-1));
}
if(k==1){
int mini[n]{},maxi[n]{};
vector<int>vals;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(x[i][j]<x[i][mini[i]])mini[i]=j;
if(x[i][j]>x[i][maxi[i]])maxi[i]=j;
}
vals.pb(x[i][mini[i]]);
vals.pb(x[i][maxi[i]]);
}
lint ans=0;
vector<int>choices;
for(int med:vals){
lint cur=0;
int cnt=0;
vector<int>curchoice(n);
vector<pii>des;
for(int i=0;i<n;i++){
if(med<x[i][mini[i]]){
cur+=abs(med-x[i][maxi[i]]);
//cerr<<x[i][maxi[i]]<<" maxi?\n";;
curchoice[i]=1;
cnt++;
}
else if(x[i][maxi[i]]<=med){
cur+=abs(med-x[i][mini[i]]);
curchoice[i]=0;
cnt--;
}else{
//cerr<<i<<" is choice\n";
cur+=abs(med-x[i][mini[i]]);
des.pb({abs(med-x[i][maxi[i]])-abs(med-x[i][mini[i]]),i});
}
}
if(des.size()<abs(cnt)){
continue;
}
sort(des.begin(),des.end());
int l=0,r=des.size()-1;
//cerr<<med<<" :: "<<cur<<"\n";
while(l<=r){
if(cnt<0){
cur+=des[r].first;
cnt++;
curchoice[des[r].second]=1;
r--;
}else{
//cur+=des[l].first;
cnt--;
curchoice[des[l].second]=0;
l++;
}
}
if(ans<cur){
ans=cur;
//cerr<<med<<" is chosen\n";
choices=curchoice;
}
}
for(int i=0;i<n;i++){
answer[i][choices[i]==1?maxi[i]:mini[i]]=0;
}
allocate_tickets(answer);
return ans;
}
return -1;
}
