#include "tickets.h"
#include <bits/stdc++.h>
#define MP make_pair
using namespace std;
bool vis[1510];
void allocate_tickets( std::vector<std::vector<int>> _d);
long long find_maximum(int k, vector<vector<int> >x) {
int n=x.size();
int m=x[0].size();
vector<vector<int> >answer(n,vector<int>(m,-1)),cnt(n,vector<int>(m));
vector<pair<int,pair<int,int> > >tmp;
for(int i=0;i<n;i++){
for(int j=0;j<k;j++){
cnt[i][j]=-1;
tmp.push_back(MP(x[i][j]+x[i][m+j-k],MP(i,j)));
}
}
nth_element(tmp.begin(),tmp.begin()+n*k/2,tmp.end());
for(int i=n*k/2;i<n*k;i++){
cnt[tmp[i].second.first][tmp[i].second.second]++;
cnt[tmp[i].second.first][m+tmp[i].second.second-k]++;
}
long long ans=0;
vector<queue<int> >add(n),del(n);
for(int i=0;i<n;i++) for(int j=0;j<m;j++){
if(cnt[i][j]<0){
del[i].push(j);
ans-=x[i][j];
}
if(cnt[i][j]>0){
add[i].push(j);
ans+=x[i][j];
}
}
for(int j=0;j<k;j++){
int delta=0;
for(int i=0;i<n;i++){
vis[i]=false;
if(add[i].empty()){
--delta;
answer[i][del[i].front()]=j;
del[i].pop();
vis[i]=true;
}
else if(del[i].empty()){
++delta;
answer[i][add[i].front()]=j;
add[i].pop();
vis[i]=true;
}
}
for(int i=0;i<n;i++){
if(vis[i]) continue;
if(delta<0){
++delta;
answer[i][add[i].front()]=j;
add[i].pop();
}
else{
--delta;
answer[i][del[i].front()]=j;
del[i].pop();
}
}
}
allocate_tickets(answer);
return ans;
}
