#include<bits/stdc++.h>
#include "tickets.h"
#define MAXN 1507
using namespace std;
const long long inf=1e15;
int n,m,sol[MAXN],k,rest[MAXN],br,maxs,ind[MAXN],cnt0,cnt1,ans;
pair<int,int> s[MAXN][MAXN];
vector<int> curr;
vector< vector<int> > res;
int used[MAXN],tim;
vector< pair<int,int> > all;
long long find_maximum(int K,vector< vector<int> > x){
n=int(x.size()); m=int(x[0].size()); k=K;
res.resize(n);
for(int i=0;i<n;i++){
res[i].resize(m); ind[i]=i;
for(int f=0;f<m;f++){
s[i][f]={x[i][f],f};
res[i][f]=-1;
all.push_back({x[i][f],i});
}
sort(s[i],s[i]+m);
}
sort(all.begin(),all.end());
for(int i=0;i<n*m/2;i++){
sol[all[i].second]++;
}
for(int i=n*m/2;i<n*m;i++){
rest[all[i].second]++;
}
for(int i=0;i<k;i++){
br=n/2; tim++;
cnt0=cnt1=0;
for(int f=0;f<n;f++){
if(sol[f]>0)cnt0++;
if(rest[f]>0)cnt1++;
}
if((cnt0>=n/2 and cnt1>=n/2) or cnt0<n/2){
for(int f=0;f<n/2;f++){
maxs=n;
for(int w=0;w<n;w++){
if(sol[w]>sol[maxs] and used[w]!=tim)maxs=w;
}
if(sol[maxs]==0)break;
res[maxs][s[maxs][sol[maxs]-1].second]=i;
sol[maxs]--; used[maxs]=tim; br--;
}
for(int f=0;f<n;f++){
if(used[f]!=tim){
res[f][s[f][m-rest[f]].second]=i; rest[f]--;
}
}
}else{
for(int f=0;f<n/2;f++){
maxs=n;
for(int w=0;w<n;w++){
if(rest[w]>rest[maxs] and used[w]!=tim)maxs=w;
}
if(rest[maxs]==0)break;
res[maxs][s[maxs][m-rest[maxs]].second]=i;
rest[maxs]--; used[maxs]=tim; br--;
}
for(int f=0;f<n;f++){
if(used[f]!=tim){
res[f][s[f][sol[f]-1].second]=i; sol[f]--;
}
}
}
}
allocate_tickets(res);
return ans;
}
/*
int main(){
cout<<find_maximum(2, {{0, 2, 5},{1, 1, 3}})<<"\n";
}
*/
