#include "tickets.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
int L[1501];
queue<int> A[1501];
queue<int> B[1501];
int ss[1501];
queue<int> aa[1501];
queue<int> bb[1501];
queue<pair<int,int>> Q[1501];
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n = x.size();
int m = x[0].size();
std::vector<std::vector<int>> answer(n);
int i,j;
for(int i=0 ; i<n ; i++)answer[i].resize(m);
for(i=0 ; i<n ; i++)for(j=0 ; j<m ; j++)answer[i][j]=-1;
priority_queue<pair<int,int>> Q2;
for(i=0 ; i<n ; i++){
for(j=1 ; j<=k ; j++){
Q[i].push({x[i][k-j]+x[i][m-j],j});
}
Q2.push({Q[i].front().first,i});
}
vector<pair<int,pair<int,int>>> v;
for(i=0 ; i<n*k/2 ; i++){
int t=Q2.top().second;
Q2.pop();
Q[t].pop();
if(!Q[t].empty())Q2.push({Q[t].front().first,t});
}
for(i=0 ; i<n ; i++){
int y;
if(Q[i].empty())y=0;
else y=Q[i].size();
for(j=0 ; j<y ; j++)v.push_back({x[i][j],{i,j}});
for(j=m-(k-y) ; j<m ; j++)v.push_back({x[i][j],{i,j}});
}
sort(v.begin(),v.end());
long long ans=0;
for(i=0 ; i<n*k/2 ; i++){
aa[v[i].second.first].push(v[i].second.second);
ans-=v[i].first;
}
for(i=n*k/2 ; i<n*k ; i++){
bb[v[i].second.first].push(v[i].second.second);
ans+=v[i].first;
}
for(j=0 ; j<k ; j++){
vector<pair<int,int>> vv;
for(i=0 ; i<n ; i++)vv.push_back({bb[i].size(),i});
sort(vv.begin(),vv.end());
for(i=0 ; i<n/2 ; i++){
answer[vv[i].second][aa[vv[i].second].front()]=j;
aa[vv[i].second].pop();
}
for(i=n/2 ; i<n ; i++){
answer[vv[i].second][bb[vv[i].second].front()]=j;
bb[vv[i].second].pop();
}
}
allocate_tickets(answer);
return ans;
}
