#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
void usun(vector<int>&ile, set<pair<int, int>>&ilejedynek, int x){
pair<int,int> it = {ile[x], x};
ilejedynek.erase(it);
ile[it.second]--;
ilejedynek.insert({it.first-1, it.second});
}
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n = x.size();
int m = x[0].size();
int i, j;
set<pair<int,int>>ilejedynek;
vector<int>ile;
for(i=0;i<n;i++){
int suma = 0;
for(j=0;j<m;j++)
suma+=x[i][j];
ilejedynek.insert({suma, i});
ile.push_back(suma);
}
// for(i=0;i<n;i++)printf("%d ", ile[i]);
vector<std::vector<int>> answer(n);
int r = m;
int wynik=0;
for(int i=0;i<k;i++){
int pom = 0;
for(j=0;j<n/2;j++)
if((*ilejedynek.rbegin()).first>0){
auto it = *ilejedynek.rbegin();
answer[it.second].push_back(1);
usun(ile, ilejedynek, it.second);
pom++;
}
for(j=0;j<n;j++)
if((int)answer[j].size()<=i){
if(ile[j]==r){
answer[j].push_back(1);
usun(ile, ilejedynek, j);
pom++;
}
else{
answer[j].push_back(0);
}
}
wynik+=min(pom, n-pom);
r--;
}
// for(i=0;i<n;i++)printf("%d ", ile[i]);
for(i=0;i<n;i++){
while(ile[i]){
answer[i].push_back(1);
ile[i]--;
}
while((int)answer[i].size()<m)
answer[i].push_back(0);
}
// for(i=0;i<n;i++)printf("%d ", answer[i].size());
allocate_tickets(answer);
return wynik;
}
