#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
long long ans1 = 0;
int ptr1[1505], ptr2[1505];
int used[1505];
set<int> used2[1505];
priority_queue< pair<long long, int> > pq;
vector< vector<int> > ans2;
vector<int> ord;
bool cmp(int x, int y) {
return ptr1[x] > ptr1[y];
}
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n = x.size();
int m = x[0].size();
for(int i=0; i<n; i++) {
for(int j=0; j<k; j++) {
ans1 -= x[i][j];
}
ptr1[i] = k-1;
ptr2[i] = m-1;
pq.push({x[i][ptr1[i]]+x[i][ptr2[i]], i});
}
for(int i=0; i<k*(n/2); i++) {
int curr = pq.top().second;
ans1 += pq.top().first;
pq.pop();
ptr1[curr]--;
ptr2[curr]--;
if(ptr1[curr] >= 0) {
pq.push({x[curr][ptr1[curr]]+x[curr][ptr2[curr]], curr});
}
}
ans2.resize(n);
for(int i=0; i<n; i++) {
ans2[i].resize(m);
for(int j=0; j<m; j++) {
ans2[i][j] = -1;
}
for(int j=0; j<k; j++) used2[i].insert(j);
ord.push_back(i);
}
sort(ord.begin(), ord.end(), cmp);
for(int i:ord) {
int tmp = 0;
for(int j=0; j<=ptr1[i]; j++) {
while(used[tmp] == n/2) tmp++;
ans2[i][j] = tmp;
used[tmp]++;
used2[i].erase(tmp);
tmp++;
}
}
for(int i=0; i<n; i++) {
for(int j=ptr2[i]+1; j<m; j++) {
ans2[i][j] = (*used2[i].begin());
used2[i].erase(used2[i].begin());
}
}
allocate_tickets(ans2);
return ans1;
}
