#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
long long find_maximum(int k, vector<vector<int>> x) {
int n = (int)x.size();
int m = (int)x[0].size();
vector<vector<int>> ans(n, vector<int>(m, -1));
vector<pair<int, int>> rng(n, {0, m-1});
ll res = 0;
vector<vector<int>> ones(m+1);
for(int i = 0; i < n; i++){
int cnt = 0;
for(int j = 0; j < m; j++){
if(x[i][j]) cnt++;
}
// cout << "i " << i << " cnt " << cnt << "\n";
ones[cnt].push_back(i);
}
for(int r = 0; r < k; r++){
vector<bool> done(n, false);
int lft = n/2;
ll one = 0, zero = 0;
vector<pair<int, int>> add;
// cout << "r " << r << " ones:\n";
// for(int i = m; i >= 1; i--){
// cout << "i " << i << ": ";
// for(int x : ones[i]) cout << x << " ";
// cout << "\n";
// }
for(int i = m; i >= 1 && lft > 0; i--){
while(lft > 0 && !ones[i].empty()){
int row = ones[i].back(); ones[i].pop_back();
add.push_back({row, i-1});
done[row] = true;
lft--;
}
}
for(pair<int, int> p : add){
if(p.second >= 0) ones[p.second].push_back(p.first);
}
for(int i = 0; i < n; i++){
if(done[i]){
one++;
ans[i][rng[i].second] = r;
rng[i].second--;
}else{
if(x[i][rng[i].first]) one++;
else zero++;
ans[i][rng[i].first] = r;
rng[i].first++;
}
}
// cout << "r " << r << " zero "<< zero << " one " << one << "\n";
res += min(zero, one);
}
allocate_tickets(ans);
return res;
}
