#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
typedef pair <int,int> ii;
long long find_maximum(int k, std::vector<std::vector<int>> X)
{
int n = X.size();
int m = X[0].size();
vector <pair <int,ii> > x;
for(int i=0;i<n;i++)
{
for(int j=0;j<m;j++)
{
x.pb(make_pair(X[i][j],ii(i,j)));
}
}
sort(x.begin(),x.end());
vector <vector <ii> > small_values(n);
vector <vector <ii> > big_values(n);
for(int i=0;i<n*m/2;i++)
{
small_values[x[i].second.first].pb(ii(x[i].first,x[i].second.second));
}
for(int i=n*m/2;i<n*m;i++)
{
big_values[x[i].second.first].pb(ii(x[i].first,x[i].second.second));
}
/*for(int i=0;i<n;i++)
{
for(int j=0;j<small_values[i].size();j++)
{
printf("%d %d ",small_values[i][j].first,small_values[i][j].second);
}
printf(" ");
for(int j=0;j<big_values[i].size();j++)
{
printf("%d %d ",big_values[i][j].first,big_values[i][j].second);
}
printf("\n");
}*/
vector <vector <int> > answer(n,vector <int> (k,-1));
long long ans=0;
for(int i=0;i<k;i++)
{
int small=n/2;
int big=n/2;
vector <bool> t(n,0);
for(int j=0;j<n;j++)
{
if(small_values[j].size()==0)
{
t[j]=1;
big--;
ans+=big_values[j].back().first;
answer[j][big_values[j].back().second]=i;
big_values[j].pop_back();
}
else if(big_values[j].size()==0)
{
t[j]=1;
small--;
ans-=small_values[j].back().first;
answer[j][small_values[j].back().second]=i;
small_values[j].pop_back();
}
}
for(int j=0;j<n;j++)
{
if(t[j]==0)
{
if(big>0)
{
t[j]=1;
big--;
ans+=big_values[j].back().first;
answer[j][big_values[j].back().second]=i;
big_values[j].pop_back();
}
else
{
t[j]=1;
small--;
ans-=small_values[j].back().first;
answer[j][small_values[j].back().second]=i;
small_values[j].pop_back();
}
}
}
}
allocate_tickets(answer);
return ans;
}
