#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
int numsmall[1505];
long long find_maximum(int k, std::vector<std::vector<int>> X) {
int n = X.size();
int m = X[0].size();
long long ans = 0;
vector<vector<pair<int,int> > > sorted;
for (int x = 0; x<n; x++){
vector<pair<int,int> > stuff;
for (int y = 0; y<m; y++){
stuff.push_back({X[x][y],y});
}
sort(stuff.begin(),stuff.end());
sorted.push_back(stuff);
}
for (int x = 0; x<n; x++){
for (int y = m-k; y<m; y++){
ans += sorted[x][y].first;
}
}
priority_queue<pair<int,int> > pq;
for (int x = 0; x<n; x++){
pq.push({-sorted[x][m-k].first-sorted[x][0].first,x});
}
for (int x = 0; x<k*n/2; x++){
int cur = pq.top().second;
ans += pq.top().first;
pq.pop();
numsmall[cur]++;
if (numsmall[cur]<k)pq.push({-sorted[cur][m-k+numsmall[cur]].first-sorted[cur][numsmall[cur]].first,cur});
}
// printf("ans = %lld\n",ans);
std::vector<std::vector<int>> answer;
for (int i = 0; i < n; i++) {
std::vector<int> row(m);
for (int j = 0; j < m; j++) {
row[j] = -1;
}
answer.push_back(row);
}
for (int x = 0; x<k; x++){
// printf("round %d\n",x);
vector<pair<int,int> > thing;
for (int y = 0; y<n; y++){
thing.push_back({numsmall[y],y});
}
sort(thing.begin(),thing.end());
for (int y = 0; y<n/2; y++){
int cur = thing[y].second;
// printf("assigning big to %d\n",cur);
int numbig = k-x-numsmall[cur];
answer[cur][sorted[cur][m-numbig].second] = x;
}
for (int y = n/2; y<n; y++){
int cur = thing[y].second;
// printf("assigning small to %d\n",cur);
answer[cur][sorted[cur][numsmall[cur]-1].second] = x;
numsmall[cur]--;
}
}
allocate_tickets(answer);
return ans;
}
