#include "tickets.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int n, m, k;
vector<vector<int>> a;
vector<vector<int>> pos, neg;
void done(){
vector<vector<int>> s(n, vector<int>(m, -1));
pos.resize(n);
neg.resize(n);
for (int i=0; i<n; i++){
for (int j=0; j<m; j++){
if (a[i][j] == 1) pos[i].push_back(j);
if (a[i][j] == -1) neg[i].push_back(j);
}
}
for (int j=0; j<k; j++){
vector<int> v;
for (int i=0; i<n; i++) v.push_back(i);
sort(v.begin(), v.end(), [](int a, int b){return pos[a].size() < pos[b].size();});
for (int i=0; i<n/2; i++){
s[v[i]][neg[v[i]].back()] = j;
neg[v[i]].pop_back();
}
for (int i=n/2; i<n; i++){
s[v[i]][pos[v[i]].back()] = j;
pos[v[i]].pop_back();
}
}
allocate_tickets(s);
}
ll find_maximum(int k, vector<vector<int>> x){
::k = k;
n = x.size();
m = x[0].size();
a.resize(n, vector<int>(m, 0));
if (k == m){
vector<int> at;
for (int i=0; i<n; i++){
for (int j=0; j<m; j++) at.push_back(x[i][j]);
}
sort(at.begin(), at.end());
ll mid = at[k*n/2], res = 0;
int y = k*n/2;
for (int i=0; i<n; i++){
for (int j=0; j<m; j++){
if (x[i][j] >= mid && y){
a[i][j] = 1;
y--;
}
else a[i][j] = -1;
res += x[i][j]*a[i][j];
}
}
done();
return res;
}
priority_queue<pair<int,int>> pq;
ll res = 0;
for (int i=0; i<n; i++){
for (int j=0; j<k; j++){
a[i][j] = -1;
res -= x[i][j];
}
pq.push({x[i][m-1]+x[i][k-1], i});
}
vector<int> rem(n, k);
for (int i=0; i<k*n/2; i++){
pair<int,int> next = pq.top();
pq.pop();
res += next.first;
rem[next.second]--;
a[next.second][rem[next.second]] = 0;
a[next.second][m-(k-rem[next.second])] = 1;
if (rem[next.second]) pq.push({x[next.second][rem[next.second]-1]+x[next.second][m-(k-rem[next.second])-1], next.second});
}
done();
return res;
}
