#include "tickets.h"
#include <vector>
#include<bits/stdc++.h>
using namespace std;
#define rep(i,a,b) for(int i=a;i<b;i++)
typedef long long int lld;
#define trav(a,v) for(auto a:v)
queue<lld> q[1000000];
priority_queue<pair<lld,int> >pq;
pair<int,int> tot[1000000];
int F[1000000];
int L[1000000];
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n = x.size();
int m = x[0].size();
std::vector<std::vector<int>> answer;
lld ans=0;
rep(i,0,n){
F[i]=0;
L[i]=m-1;
tot[i]={0,i};
rep(j,0,k){
ans-=x[i][j];
}
for(int j=k-1;j>-1;j--){
q[i].push(x[i][j+(m-k)]+x[i][j]);
}
q[i].push(-1);
}
rep(i,0,n){
pq.push({q[i].front(),i});
}
rep(i,0,(n*k)/2){
ans+=pq.top().first;
int idx=pq.top().second;pq.pop();
q[idx].pop();
pq.push({q[idx].front(),idx});
tot[idx].first++;
}
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);
}
rep(round,0,k){
sort(tot,tot+n);
rep(i,0,n){
if(i<n/2){
answer[tot[i].second][F[tot[i].second]]=round;
F[tot[i].second]++;
}else{
answer[tot[i].second][L[tot[i].second]]=round;
L[tot[i].second]--;
tot[i].first--;
}
}
}
allocate_tickets(answer);
return ans;
}
