#include "tickets.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n, m;
n = x.size();
m = x[0].size();
vector<std::vector<int>> answer(n, vector<int>(m, -1));
vector<deque<int>> sub(n), add(n);
priority_queue<array<ll, 2>> pq;
ll ans = 0;
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(j<k){
sub[i].push_back(x[i][j]);
ans -= x[i][j];
answer[i][j] = -2;
}else{
add[i].push_back(x[i][j]);
}
}
if(add[i].size()){
pq.push({add[i].back() + sub[i].back(), i});
}else{
pq.push({2 * sub[i].back(), i});
}
}
for(int i=0; i<n*k/2; i++){
auto [val, id] = pq.top();
pq.pop();
ans += val;
answer[id][sub[id].size()-1] = -1;
answer[id][sub[id].size() + add[id].size() - 1] = -3;
add[id].push_front(sub[id].back());
sub[id].pop_back();
add[id].pop_back();
if(sub[id].size()){
if(add[id].size())
pq.push({add[id].back() + sub[id].back(), id});
else
pq.push({2 * sub[id].back(), id});
}
}
multiset<array<int, 2>> ms;
for(int i=0; i<n; i++){
int bal = 0;
for(int j=0; j<m; j++){
if(answer[i][j]==-2){
bal--;
}else if(answer[i][j]==-3){
bal++;
}
}
ms.insert({bal, i});
}
for(int i=0; i<k; i++){
multiset<array<int, 2>> nms;
int take = 0;
for(auto [bal, id]:ms){
if(take<n/2){
for(int j=0; j<m; j++){
if(answer[id][j]==-2){
answer[id][j]=i;
break;
}
}
nms.insert({bal+1, id});
}else{
for(int j=0; j<m; j++){
if(answer[id][j]==-3){
answer[id][j]=i;
break;
}
}
nms.insert({bal-1, id});
}
take++;
}
swap(ms, nms);
}
allocate_tickets(answer);
return ans;
}
