#include "tickets.h"
#include <vector>
#include <bits/stdc++.h>
// existen dos escenarios en el que la media sea maxima o en que sea minima
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
const int MAX_N=1510;
bool vis[MAX_N];
vector<vi> ti;
vector<vi> p1,p0;
int c0,c1;
void cero(int i,int ro){
int t=p0[i].size()-1;
ti[i][p0[i][t]]=ro;
p0[i].pop_back();
c0++;
}
void uno(int i,int ro){
int t=p1[i].size()-1;
ti[i][p1[i][t]]=ro;
p1[i].pop_back();
c1++;
}
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n,m;
n=x.size(); m=x[0].size();
ti.resize(n);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++) ti[i].push_back(-1);
}
p1.resize(n+1); p0.resize(n+1);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(x[i][j]) p1[i].push_back(j);
else p0[i].push_back(j);
}
}
ll ans=0;
for(int ro=0;ro<k;ro++){
c0=c1=0;
memset(vis,0,sizeof vis);
vector<ii> v0,v1;
for(int i=0;i<n;i++){
if(!p0[i].empty())
v0.push_back(ii(p0[i].size(),i));
if(!p1[i].empty())
v1.push_back(ii(p1[i].size(),i));
}
sort(v0.begin(),v0.end());
sort(v1.begin(),v1.end());
int c=0;
for(int i=v0.size()-1;i>=0;i--){
cero(v0[i].second,ro);
vis[v0[i].second]=1;
v0.pop_back();
c++;
if(c==n/2) break;
}
c=0;
for(int i=v1.size()-1;i>=0;i--){
uno(v1[i].second,ro);
vis[v1[i].second]=1;
v1.pop_back();
c++;
if(c==n/2) break;
}
while(c0+c1<n){
int t=v0.size()-1;
if(!v0.empty() && !vis[v0[t].second]){
cero(v0[t].second,ro);
vis[v0[t].second]=1;
v0.pop_back();
}
t=v1.size()-1;
if(!v1.empty() && !vis[v1[t].second]) {
uno(v1[t].second,ro);
vis[v1[t].second]=1;
v1.pop_back();
}
}
ans+=min(c0,c1);
}
allocate_tickets(ti);
return ans;
}
