#include "tickets.h"
//#include "grader.cpp"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int,int>
#define f first
#define s second
#define all(x) x.begin(),x.end()
#define _ ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n = x.size();
int m = x[0].size();
ll ans=0;
int sum=0;
for(int i=0;i<n;i++){
for(int j=m-k;j<m;j++){
ans+=x[i][j];
sum+=1;
}
}
vector<int> pos(n);
priority_queue<pair<ll,int>> pq;
for(int i=0;i<n;i++){
pq.push({-x[i][0]-x[i][m-k],i});
}
while(sum>0){
auto v=pq.top();
pq.pop();
ans+=v.f;
sum-=2;
int id=v.s;
//cout<<id<<' '<<pos[id]<<' '<<v.f<<'\n';
pos[id]++;
if(pos[id]==k) continue;
pq.push({-x[id][pos[id]]-x[id][m-k+pos[id]],id});
}
vector<pair<int,int>> a(n);
vector<int> b(n);
for(int i=0;i<n;i++){
a[i].f=pos[i];
a[i].s=i;
b[i]=k-a[i].f;
}
vector<vector<int>> res(n,vector<int>(m,-1));
for(int i=0;i<k;i++){
sort(all(a));
reverse(all(a));
vector<bool> used(n);
for(int j=0;j<n/2;j++){
a[j].f--;
res[a[j].s][a[j].f]=i;
used[a[j].s]=true;
}
for(int j=0;j<n;j++){
if(used[j]) continue;
b[j]--;
res[j][m-b[j]-1]=i;
}
}
allocate_tickets(res);
return ans;
}
