#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
#define fi first
#define se second
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(),x.end()
ll find_maximum(int k,vector<vector<int>> x){
int n=x.size();
int m=x[0].size();
vector<vector<int>> answer(n);
for(int i=0;i<n;++i)answer[i].resize(m,-1);
ll ans=0;
vector<int> npos(n);
priority_queue<ii> pq;
for(int i=0;i<n;++i){
for(int j=0;j<k;++j){
ans-=x[i][j];
pq.push({x[i][m+j-k]+x[i][j],i});
}
}
for(int i=0;i<n*k/2;++i){
ans+=pq.top().fi;
++npos[pq.top().se];
pq.pop();
}
vector<vector<int>> have(k);
for(int i=0;i<k;++i)have[i].resize(n);
int cur=0;
for(int i=0;i<n;++i){
for(int j=m-1;j>=m-npos[i];--j){
answer[i][j]=cur;
have[cur][i]=1;
cur=(cur+1)%k;
}
}
for(int i=0;i<n;++i){
int cur=0;
for(int j=0;j<k;++j){
if(!have[j][i]){
answer[i][cur]=j;
++cur;
}
}
}
allocate_tickets(answer);
return ans;
}
