#include"tickets.h"
#include<iostream>
#include<vector>
#include<queue>
#include<stack>
#include<algorithm>
#include<limits.h>
#include<math.h>
#include<map>
#include<set>
#include<unordered_map>
#include<unordered_set>
#include<iomanip>
using namespace std;
typedef long long ll;
ll find_maximum(int k,vector<vector<int>>x){
ll n=x.size();
ll m=x[0].size();
vector<vector<int>>answer(n,vector<int>(m,-1));
vector<vector<pair<ll,ll>>>arr(n,vector<pair<ll,ll>>(m));
ll sum=0;
vector<pair<ll,ll>>q;
vector<ll>numplus(n,0);
for(ll i=0;i<n;i++){
for(ll j=0;j<m;j++){
arr[i][j]={x[i][j],j};
}
sort(arr[i].begin(),arr[i].end());
for(ll 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());
for(ll i=n*k-1;i>=n*k/2;i--){
sum+=q[i].first;
numplus[q[i].second]++;
}
vector<ll>numtaken1(n,0);
vector<ll>numtaken2(n,0);
for(int round=0;round<k;round++){
int num_down=0;
for(ll 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;
}
