#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
using vi = vector<int>;
using ll = long long;
using ii = pair<int, int>;
using vll = vector<ll>;
ll find_maximum(int k, vector<vi> x) {
int n = x.size();
int m = x[0].size();
vll Sum(n, 0), CntPlus(n, 0);
auto calc = [&](int cul, int nr) { // cat as castiga
return x[cul][m - 1 - nr] + x[cul][k - 1 - nr];
};
priority_queue<pair<ll, int> > PQ;
for(int i = 0; i < n; ++i) {
for(int j = 0; j < k; ++j) {
Sum[i] -= x[i][j];
}
PQ.push({calc(i, 0), i});
}
for(int nr = 0; nr < n * k / 2; ++nr) {
auto [delta, cul] = PQ.top();
PQ.pop();
++CntPlus[cul];
Sum[cul] += delta;
if(CntPlus[cul] < k) {
PQ.push({calc(cul, CntPlus[cul]), cul});
}
}
ll re = 0;
for(auto it : Sum) re += it;
vector<vector<ii>> Plus(n), Minus(n);
vector<vi> S(n, vi(m, -1));
for(int i = 0; i < n; ++i) {
for(int j = 0; j < k - CntPlus[i]; ++j)
Minus[i].push_back({i, j});
for(int j = 0; j < CntPlus[i]; ++j)
Plus[i].push_back({i, m - 1 - j});
}
for(int nr = 0; nr < k; ++nr) {
vi Neutre;
vector<ii> Luate;
int sum = 0;
vi ord;
for(int i = 0; i < n; ++i) {
ord.push_back(i);
}
sort(ord.begin(), ord.end(), [&](auto a, auto b) {
return abs((int)Plus[a].size() - (int)Minus[a].size())
> abs((int)Plus[b].size() - (int)Minus[b].size());
});
for(int i = 0; i < n; ++i) {
int it = ord[i], ramase = n - i;
if((sum != ramase && Plus[it].size() > Minus[it].size()) || sum == -ramase) {
Luate.push_back(Plus[it].back());
Plus[it].pop_back();
++sum;
} else {
Luate.push_back(Minus[it].back());
Minus[it].pop_back();
--sum;
}
}
vi Val;
for(auto [c, p] : Luate) {
S[c][p] = nr;
Val.push_back(x[c][p]);
}
}
allocate_tickets(S);
return re;
}
