#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
priority_queue<pair<long long, long long> > pq;
pair<long long, long long> CNT[1505];
vector<vector<int> > ans;
long long cnt[1505];
bool chosen[1505];
vector<int> tmp;
long long find_maximum(int K, vector<vector<int> > X)
{
long long N=X.size(), M=X[0].size(), sum=0;
for (long long i=0; i<N; i++)
for (long long j=0; j<K; j++)
sum-=X[i][j];
for (long long i=0; i<N; i++)
pq.push({X[i][K-1]+X[i][M-1], i});
for (long long i=0; i<N*K/2; i++)
{
long long p=pq.top().first, q=pq.top().second;
pq.pop();
sum+=p;
cnt[q]++;
if (cnt[q]<K)
pq.push({X[q][K-cnt[q]-1]+X[q][M-cnt[q]-1], q});
}
for (long long i=0; i<N; i++)
{
tmp.clear();
for (long long j=0; j<M; j++)
tmp.push_back(-1);
ans.push_back(tmp);
}
for (long long i=0; i<N; i++)
CNT[i]={cnt[i], i};
sort(CNT, CNT+N, greater<pair<long long, long long> >());
for (long long i=0; i<K; i++)
{
for (long long j=0; j<N; j++)
chosen[j]=0;
long long index=0;
for (long long j=0; j<N/2; j++)
{
while (CNT[index].first<CNT[index+1].first)
index++;
long long q=CNT[index].second;
chosen[q]=1;
ans[q][M-cnt[q]]=i;
cnt[q]--;
CNT[index].first--;
index++;
}
for (long long j=0; j<N; j++)
if (!chosen[j])
ans[j][K-i-cnt[j]-1]=i;
}
allocate_tickets(ans);
return sum;
}
