#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n = x.size();
int m = x[0].size();
int i, j;
vector<vector<int>>answer = x;
for(i=0;i<n;i++)
for(j=0;j<m;j++)
answer[i][j] = -1;
long long wynik = 0;
priority_queue<pair<long long, pair<int, int>>>kolejka;
vector<set<int>>dodatnie(n), ujemne(n);
for(i=0;i<n;i++){
for(j=m-k;j<m;j++){
wynik+=x[i][j];
dodatnie[i].insert(j);
}
kolejka.push({-(long long)x[i][m-k]-x[i][0], {i, 0}});
}
// int dl = m-k;
for(int minus=0;minus<k*n/2;minus++){
i = kolejka.top().second.first;
j = kolejka.top().second.second;
wynik+=kolejka.top().first;
// printf("%d %d %d\n", i, j, wynik);
kolejka.pop();
ujemne[i].insert(j);
dodatnie[i].erase(j+m-k);
j++;
if(j<k)
kolejka.push({-(long long)x[i][m-k+j]-x[i][j], {i,j}});
}
// for(i=0;i<n;i++){
// for(auto j: ujemne[i])printf("%d ", j);printf("\n");
// for(auto j: dodatnie[i])printf("%d ", j);printf("\n");
//} //exit(0);
//0011111
//1111100
set<pair<int,int>>najwiecej;
for(i=0;i<k;i++){
najwiecej.clear();
for(j=0;j<n;j++)najwiecej.insert({dodatnie[j].size(), j});
for(int ij=0;ij<n;ij++){
j = (*najwiecej.rbegin()).second;
najwiecej.erase(*najwiecej.rbegin());
if(ij<n/2){
auto it = *dodatnie[j].begin();
answer[j][it] = i;
dodatnie[j].erase(it);
}
else{
auto it = *ujemne[j].begin();
answer[j][it] = i;
ujemne[j].erase(it);
}
}
}
vector<vector<int>>res = x;
long long w2 = 0;
for(i=0;i<n;i++)
for(j=0;j<m;j++){
if(answer[i][j]>=0)
res[i][answer[i][j]] = x[i][j];
}
for(i=0;i<k;i++){
vector<int>wiersz;
for(j=0;j<n;j++)
wiersz.push_back(res[j][i]);
sort(wiersz.begin(), wiersz.end());
for(j=0;j<n;j++)
if(j<n/2)
w2-=wiersz[j];
else
w2+=wiersz[j];
}
// if(w2!=wynik)printf("%d %d!!!\n", wynik, w2);
// exit(0);
allocate_tickets(answer);
return wynik;
}
