#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);
vector<int> ones(N,0);
for(int i = 0;i < N;i++){
for(auto &j:x[i]) ones[i] += j;
}
for(int ck = 0;ck < k;ck++){
vector<pair<int,int>> colors;// cone,idx;
for(int i = 0;i < N;i++){
colors.push_back({ones[i],i});
}
sort(colors.begin(),colors.end());
for(int i = 0;i < N;i++){
// cout << type[i];
auto [cone,cidx] = colors[i];
if(i < N/2){// take zero
answer[cidx][fpt[cidx]] = ck;
//ones[cidx] -= answer[cidx][fpt[cidx]];
ones[cidx] = min(ones[cidx],k-(ck+1));
fpt[cidx]++;
}else{// take one
answer[cidx][bpt[cidx]] = ck;
ones[cidx] --;
bpt[cidx]--;
}
}
}
return m_allocate_tickets(answer,x);
}
