#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 <priority_queue <ii> > smalls(n);
vector <priority_queue <ii> > bigs(n);
for(int i=0;i<n;i++)
{
sort(x[i].begin(),x[i].end());
for(int j=0;j<m-k;j++)
{
smalls[i].push(ii(-x[i][j],j));
}
for(int j=m-k;j<m;j++)
{
bigs[i].push(ii(-x[i][j],j));
}
}
priority_queue <ii> pq;
for(int i=0;i<n;i++)
{
int best=bigs[i].top().first*2;
if(smalls[i].size())
{
best=max(best,bigs[i].top().first+smalls[i].top().first);
}
pq.push(ii(best,i));
}
vector <vector <ii> > small_values(n);
vector <vector <ii> > big_values(n);
for(int i=0;i<n*k/2;i++)
{
int loc=pq.top().second;
pq.pop();
int val=bigs[loc].top().first;
int loc2=bigs[loc].top().second;
bigs[loc].pop();
smalls[loc].push(ii(val,loc2));
small_values[loc].pb(smalls[loc].top());
smalls[loc].pop();
if(bigs[loc].size())
{
int best=bigs[loc].top().first*2;
if(smalls[loc].size())
{
best=max(best,bigs[loc].top().first+smalls[loc].top().first);
}
pq.push(ii(best,loc));
}
}
for(int i=0;i<n;i++)
{
while(bigs[i].size())
{
big_values[i].pb(bigs[i].top());
bigs[i].pop();
}
}
/*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> (m,-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;
}
