#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
void allocate_tickets( std::vector<std::vector<int>> _x);
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n = x.size();
int m = x[0].size();
vector<deque<pair<ll,ll>>> q;
for(auto&i:x){
q.emplace_back();
int idx = 0;
for(int&j:i)q.back().emplace_back(j,idx++);
}
vector<vector<int>> anss(n,vector<int>(m,-1));
ll ans=0;
for(int round=0;round<k;round++){
vector<bool> status(n); //True means max taken
priority_queue<tuple<ll,int,ll>> deltaq;
for(int i=0;i<n;i++){
ans-=q[i].front().first;
int pri = 0;
if(q[i].size()>1 and q[i].back().first==q[i][q[i].size()-2].first)pri=2;
else if(q[i].size()>1 and q[i][0].first!=q[i][1].first)pri=1;
deltaq.emplace(q[i].back().first+q[i].front().first,pri,i);
}
for(int i=0;i<n/2;i++){
auto [change,pri,idx] = deltaq.top();deltaq.pop();
ans+=change;
status[idx]=true;
}
for(int i=0;i<n;i++){
if(status[i]){
anss[i][q[i].back().second]=round;
q[i].pop_back();
} else {
anss[i][q[i].front().second]=round;
q[i].pop_front();
}
}
}
allocate_tickets(anss);
return ans;
}
