#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;
for(int i = 0; i < n; ++i) {
if(Plus[i].size() == Minus[i].size()) {
Neutre.push_back(i);
continue;
}
if(Plus[i].size() > Minus[i].size()) {
Luate.push_back(Plus[i].back());
Plus[i].pop_back();
++sum;
} else {
Luate.push_back(Minus[i].back());
Minus[i].pop_back();
--sum;
}
}
for(auto i : Neutre) {
if(sum < 0) {
Luate.push_back(Plus[i].back());
Plus[i].pop_back();
++sum;
} else {
Luate.push_back(Minus[i].back());
Minus[i].pop_back();
--sum;
}
}
vi Val;
for(auto [c, p] : Luate) {
S[c][p] = nr;
Val.push_back(x[c][p]);
}
sort(Val.begin(), Val.end());
for(int i = 0; i < n; ++i) {
if(i < n / 2) re -= Val[i];
else re += Val[i];
}
}
allocate_tickets(S);
return re;
}
