#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
long long m_allocate_tickets(vector<vector<int>> answer,vector<vector<int>> x){
allocate_tickets(answer);
// find k;
int N = answer.size();
int k = 0;
for(auto &i:answer[0]) k = max(i+1,k);
vector<vector<int>> cards(k);
for(int i = 0;i < N;i++){
for(int j = 0;j < answer[0].size();j++){
if(answer[i][j] != -1) cards[answer[i][j]].push_back(x[i][j]);
}
}
long long ans = 0;
for(auto v:cards) {
sort(v.begin(),v.end());
for(int i = 0;i < N;i++){
if(i < N/2){
ans -= v[i];
}else{
ans += v[i];
}
}
}
return ans;
}
long long find_maximum(int k, vector<vector<int>> x) {
int N = x.size();
int M = x[0].size();
vector<vector<int>> answer(N,vector<int>(M,-1));
vector<int> fpt(N,0);
vector<int> bpt(N,M-1);
for(int ck = 0;ck < k;ck++){
vector<array<int,3>> colors;// big,small,idx;
for(int i = 0;i < N;i++){
colors.push_back({x[i][bpt[i]],x[i][fpt[i]],i});
}
sort(colors.begin(),colors.end());
priority_queue<pair<int,int>> pq;// -big-small,idx
for(auto [big,small,idx]:colors){
// cout << "!" << big << " " << small << " " << idx << endl;
if(pq.size() < N/2) pq.push({-big-small,idx});
else {
auto [minus,pidx] = pq.top();
if(big+minus > -small) {
pq.pop();
pq.push({-big-small,idx});
}
}
}
vector<int> type(N,0);// 0:small,1:big;
while(!pq.empty()){
auto [minus,pidx] = pq.top();
pq.pop();
type[pidx] = 1;
}
for(int i = 0;i < N;i++){
// cout << type[i];
if(type[i]){
answer[i][bpt[i]] = ck;
bpt[i]--;
}else{
answer[i][fpt[i]] = ck;
fpt[i]++;
}
}
}
return m_allocate_tickets(answer,x);
}
