#include<bits/stdc++.h>
#include "tickets.h"
using namespace std;
int k,n,m,n2;
vector<vector<int>>answer;
vector<vector<pair<int,int>>>Tab;
int miejsce[1509];
vector<int>V1[1509],V2[1509];
int CzyWziete[1509];
long long find_maximum(int K, vector<vector<int>>A)
{
k=K;
n = A.size();
n2=n/2;
m = A[0].size();
answer.resize(n,vector<int>(m,-1));
for(int i=0;i<n;i++)
{
vector<pair<int,int>>Temp;
for(int j=0;j<m;j++)
{
Temp.push_back({A[i][j],j});
}
sort(Temp.begin(),Temp.end());
Tab.push_back(Temp);
}
long long wynik=0;
const int kij=m-k;
for(int i=0;i<n;i++)
{
for(int j=kij;j<m;j++)
{
wynik+=Tab[i][j].first;
}
}
set<pair<int,int>>S;
for(int i=0;i<n;i++)
{
miejsce[i]=0;
S.insert({Tab[i][0].first+Tab[i][kij].first,i});
}
for(int I=1;I<=n*k/2;I++)
{
pair<int,int>xd=*S.begin();
S.erase(xd);
wynik-=xd.first;
miejsce[xd.second]++;
if(miejsce[xd.second]+kij<m)
{
S.insert({Tab[xd.second][miejsce[xd.second]].first+Tab[xd.second][miejsce[xd.second]+kij].first,xd.second});
}
}
for(int i=0;i<n;i++)
{
for(int j=0;j<miejsce[i];j++)
{
V1[i].push_back(Tab[i][j].second);
}
for(int j=miejsce[i]+kij;j<m;j++)
{
V2[i].push_back(Tab[i][j].second);
}
}
memset(CzyWziete,-1,sizeof(CzyWziete));
for(int i=0;i<k;i++)
{
int IleMalych=n2;
for(int j=0;j<n;j++)
{
if((int)V1[j].size()==0)
{
answer[j][V2[j].back()]=i;
V2[j].pop_back();
CzyWziete[j]=i;
}
else if((int)V2[j].size()==0)
{
answer[j][V1[j].back()]=i;
V1[j].pop_back();
CzyWziete[j]=i;
IleMalych--;
}
}
for(int j=0;j<n;j++)
{
if(CzyWziete[j]==i){continue;}
if(IleMalych>0)
{
answer[j][V1[j].back()]=i;
V1[j].pop_back();
IleMalych--;
}
else
{
answer[j][V2[j].back()]=i;
V2[j].pop_back();
}
}
}
allocate_tickets(answer);
return wynik;
}
