#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN = 1505;
int n, m, cnt0[MAXN], cnt1[MAXN];
vector<vector<int>> ans;
ll total_prize;
long long find_maximum(int k, vector<vector<int>> x) {
n = x.size(); m = x[0].size();
ans.assign(n, vector<int>(m, -1));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if(x[i][j] == 0) cnt0[i]++;
else cnt1[i]++;
}
}
for(int r = 0; r < k; r++){
vector<int> escolhe1, escolhe0;
for(int i = 0; i < n; i++){
if(cnt0[i] == 0){//preciso pegar 1
escolhe1.push_back(i);
}
else if(cnt1[i] == 0){//preciso pegar 0
escolhe0.push_back(i);
}
}
for(int i = 0; i < n; i++){
if(cnt0[i] == 0 || cnt1[i] == 0) continue;
if(escolhe0.size() < escolhe1.size()) escolhe0.push_back(i);
else escolhe1.push_back(i);
}
// cerr << "Rodada " << r << endl;
// cerr << "Escolhi 0 dos: ";
// for(int e : escolhe0) {cerr << e << " ";} cerr << endl;
// cerr << "Escolhi 1 dos: ";
// for(int e : escolhe1) {cerr << e << " ";} cerr << endl;
for(int e : escolhe0){
cnt0[e]--;
ans[e][cnt0[e]] = r;
}
for(int e : escolhe1){
ans[e][m-cnt1[e]] = r;
cnt1[e]--;
}
total_prize += min(escolhe0.size(), escolhe1.size());
}
allocate_tickets(ans);
return total_prize;
}
