#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
long long find_maximum(int k, vector<vector<int>> v) {
int n = v.size();
int m = v[0].size();
vector<vector<int>> ans;
multiset<int> st[n];
vector<int> sm[n],bg[n];
priority_queue<pair<int,int>> q;
for(int i=0;i<n;i++){
vector<int> row(m);
for(int j=0;j<m;j++){
row[j]=-1;
st[i].insert(v[i][j]);
}
int j=0;
for(auto it=st[i].begin();j<k;j++,it++){
sm[i].push_back(*it);
}
q.push({(*st[i].rbegin())+sm[i].back(),i});
ans.push_back(row);
}
for(int t=0;t<k*n/2;t++){
int i=q.top().second; q.pop();
sm[i].pop_back(); bg[i].push_back(*st[i].rbegin());
st[i].erase(prev(st[i].end()));
if(!sm[i].size()) continue;
q.push({(*st[i].rbegin())+sm[i].back(),i});
}
int arr[k]={}; map<int,int> mp;
int vis[n][k+5]={};
long long sum=0; int fill=0;
for(int i=0;i<n;i++){
int idx=fill,temp=fill;
for(auto x:sm[i]){
sum-=x; mp[x]++;
arr[idx]++;
if(arr[idx]==n/2) fill=idx+1;
idx++;
}
idx=temp;
for(int j=0;j<m;j++){
if(mp[v[i][j]]==0) continue;
vis[i][idx]++;
mp[v[i][j]]--; ans[i][j]=idx;
idx++;
}
mp.clear();
}
for(int i=0;i<k;i++) arr[i]=0;
for(int i=0;i<n;i++){
int idx=0;
for(auto x:bg[i]){
while(vis[i][idx]||arr[idx]==n/2) idx++;
sum+=x; mp[x]++;
idx++;
}
idx=0;
for(int j=0;j<m;j++){
while(vis[i][idx]||arr[idx]==n/2) idx++;
if(mp[v[i][j]]==0) continue;
arr[idx]++;
mp[v[i][j]]--; ans[i][j]=idx;
idx++;
}
mp.clear();
}
allocate_tickets(ans);
return sum;
}
