#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
long long find_maximum(int k, vector<vector<int>> x) {
int n = x.size();
int m = x[0].size();
long long ret = 0;
vector<int> tot0(n);
vector<int> tot1(n);
set<array<int, 3>> se;
for (int i = 0; i < n; ++i) {
tot0[i] = count(x[i].begin(), x[i].end(), 0);
tot1[i] = m - tot0[i];
se.insert({-tot0[i], tot1[i], i});
}
vector<int> taken_zeros(n);
for (int rep = 0; rep < k; ++rep) {
int need = 0;
int need1 = 0;
for (auto [rem0, rem1, idx] : se) {
rem0 = -rem0;
if (rem0 > 0 && (rem1 == 0 || need < n / 2)) {
need++;
taken_zeros[idx]++;
} else {
need1++;
}
}
ret += min(need, need1);
se.clear();
for (int i = 0; i < n; ++i) {
se.insert({-(tot0[i] - taken_zeros[i]), tot1[i] - (rep + 1 - taken_zeros[i]), i});
}
}
vector<vector<int>> answer(n, vector<int> (m, -1));
for (int i = 0; i < n; ++i) {
int cnt = 0;
for (int j = 0; j < taken_zeros[i]; ++j) {
answer[i][j] = cnt++;
}
int taken_ones = k - taken_zeros[i];
for (int j = m - taken_ones; j < m; ++j) {
answer[i][j] = cnt++;
}
assert(cnt == k);
}
allocate_tickets(answer);
return ret;
}
