#include "tickets.h"
#include <vector>
#include <iostream>
#include <algorithm>
using ll = long long;
struct Change {
int delta, i, j;
bool operator < (const Change &other) const {
return delta > other.delta;
};
};
ll find_maximum(int k, std::vector<std::vector<int>> a) {
int n = (int) a.size();
int m = (int) a[0].size();
std::vector<std::vector<int>> answer(n, std::vector<int>(m, -1));
std::vector<int> cntneg(n, k);
std::vector<int> cntpos(n, 0);
ll sum = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < k; j++) {
sum += -a[i][j];
}
}
std::vector<Change> deltas;
for (int i = 0; i < n; i++) {
for (int alcatelea = 1; alcatelea <= k; alcatelea++) {
int apare = m - alcatelea;
int dispare = k - alcatelea;
if (apare < k) {
break;
}
deltas.push_back({a[i][apare] + a[i][dispare], i, apare});
}
}
std::sort(deltas.begin(), deltas.end());
for (int i = 0; i < n * k / 2; i++) {
auto [increase, row, apare] = deltas[i];
sum += increase;
cntpos[row]++;
cntneg[row]--;
}
std::vector<int> pozitive = cntpos;
std::vector<int> negative = cntneg;
for (int round = 0; round < k; round++) {
std::vector<int> rows;
for (int i = 0; i < n; i++) {
rows.push_back(i);
}
std::sort(rows.begin(), rows.end(), [&](int x, int y) {
return cntpos[x] > cntpos[y];
});
for (int i = 0; i < n / 2; i++) {
answer[rows[i]][m - cntpos[rows[i]]--] = round;
}
for (int i = n / 2; i < n; i++) {
answer[rows[i]][--cntneg[rows[i]]] = round;
}
}
allocate_tickets(answer);
return sum;
}
