#include<bits/stdc++.h>
#include "tickets.h"
#include <vector>
using namespace std;
const int N = 1510;
int ans[N][N];
int l[N], r[N];
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n = x.size();
int m = x[0].size();
std::vector<std::vector<int>> answer;
vector <array <int, 3>> trip;
for(int i = 0;i < n;i++){
int qtd0 = 0, qtd1 = 0;
l[i] = 0, r[i] = m-1;
for(int j = 0;j < m;j++){
if(x[i][j] == 0) qtd0++;
else qtd1++;
}
trip.push_back({qtd0, qtd1, i});
}
memset(ans, -1, sizeof ans);
int at = 0;
long long res = 0;
while(k > 0){
int cnt0 = 0, cnt1 = 0;
for(auto [a, b, c] : trip){
if(a > 0) cnt0++;
if(b > 0) cnt1++;
}
if(cnt0 > cnt1){
for(auto &p : trip){
if(p[0] > 0){
ans[p[2]][l[p[2]]] = at;
l[p[2]]++;
p[0]--;
}
else{
ans[p[2]][r[p[2]]] = at;
r[p[2]]--;
p[1]--;
}
}
at++;
res += cnt1;
}
else{
for(auto &p : trip){
if(p[1] == 0){
ans[p[2]][l[p[2]]] = at;
l[p[2]]++;
p[0]--;
}
else{
ans[p[2]][r[p[2]]] = at;
r[p[2]]--;
p[1]--;
}
}
at++;
res += cnt0;
}
k--;
}
for(int i = 0;i < n;i++){
vector <int> aux;
for(int j = 0;j < m;j++){
aux.push_back(ans[i][j]);
}
answer.push_back(aux);
}
allocate_tickets(answer);
return res;
}
