#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;
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;
deque<int> ord;
for(int i=0;i<n;i++){
if(!p1[i].empty() && !p0[i].empty()){
ord.push_back(i);
}
else{
ord.push_front(i);
}
}
while(!ord.empty()){
int i=ord.front();
ord.pop_front();
if(!p1[i].empty() && !p0[i].empty()){
if(c0<c1){
cero(i,ro);
}
else{
uno(i,ro);
}
}
else{
if(!p1[i].empty()) uno(i,ro);
else cero(i,ro);
}
}
ans+=min(c0,c1);
}
allocate_tickets(ti);
return ans;
}
