#include "tickets.h"
#include <bits/stdc++.h>
typedef std::pair<int,int> pii;
#define x first
#define y second
std::vector<pii> vt[1505];
int cur[1505],id[1505];
std::priority_queue<pii> pq;
void Push(int x,int k,int m){
if(cur[x]>k)return;
pq.push(std::make_pair(vt[x][k-cur[x]].x+vt[x][m-cur[x]].x,x));
}
std::vector<int> vd[1505],va[1505];
long long find_maximum(int k, std::vector<std::vector<int>> a) {
int n = a.size();
int m = a[0].size();
std::vector<std::vector<int>> answer(n,std::vector<int>(m,-1));
long long ans=0;
for(int i=0;i<n;++i){
vt[i].resize(m);
for(int j=0;j<m;++j)vt[i][j]=std::make_pair(a[i][j],j);
std::sort(vt[i].begin(),vt[i].end());
for(int j=0;j<k;++j){ans-=vt[i][j].x;}
cur[i]=1;
Push(i,k,m);
}
int w=(n>>1)*k,hn=n>>1;
for(int i=0;i<w;++i){
ans+=pq.top().x;
int id=pq.top().y;
pq.pop();
++cur[id];
Push(id,k,m);
}
for(int i=0;i<n;++i){
for(int j=0;j<=k-cur[i];++j)vd[i].emplace_back(vt[i][j].y);
for(int j=m-cur[i]+1;j<m;++j)va[i].emplace_back(vt[i][j].y);
id[i]=i;
}
for(int i=0;i<k;++i){
std::sort(id,id+n,[](int x,int y){return vd[x].size()<vd[y].size();});
for(int j=0;j<hn;++j){
answer[id[j]][va[id[j]].back()]=i;
va[id[j]].pop_back();
}
for(int j=hn;j<n;++j){
answer[id[j]][vd[id[j]].back()]=i;
vd[id[j]].pop_back();
}
}
allocate_tickets(answer);
return ans;
}
