#include"tickets.h"
#include<vector>
#include<algorithm>
using namespace std;
typedef long long ll;
ll find_maximum(int k,vector<vector<int>>x){
int n=(int)x.size();
int m=(int)x[0].size();
vector<vector<int>>answer(n,vector<int>(m,-1));
vector<vector<pair<int,int>>>arr(n,vector<pair<int,int>>(m));
ll sum=0;
vector<pair<int,int>>q;
vector<int>numplus(n);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
arr[i][j]={x[i][j],j};
}
sort(arr[i].begin(),arr[i].end());
for(int j=0;j<k;j++){
sum-=arr[i][j].first;
q.emplace_back(arr[i][j].first+arr[i][m-k+j].first,i);
}
}
sort(q.begin(),q.end());
reverse(q.begin(),q.end());
q.resize(n*k/2);
for(auto i:q){
sum+=i.first;
numplus[i.second]++;
}
vector<int>numtaken1(n);
vector<int>numtaken2(n);
for(int round=0;round<k;round++){
int num_down=0;
for(int i=0;i<n;i++){
if(num_down==n/2||numtaken1[i]==k-numplus[i]){
numtaken2[i]++;
answer[i][m-numtaken2[i]]=round;
}else{
answer[i][numtaken1[i]]=round;
numtaken1[i]++;
num_down++;
}
}
}
allocate_tickets(answer);
return sum;
}
