#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define len(v) (int) (v.size())
#define all(v) v.begin(), v.end()
using ll = long long;
long long find_maximum(int k, vector<vector<int>> x) {
int n = len(x);
int m = len(x[0]);
vector answer(n, vector(m, -1));
vector<pair<int, int>> cell(n * m);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
cell[i * m + j] = {x[i][j], i};
}
}
sort(all(cell));
vector<int> cnt(n, 0);
int r = n * k / 2;
for (int i = len(cell) - 1; i >= 0 && r > 0; i--) {
if (cnt[cell[i].second] < k) {
cnt[cell[i].second]++;
r--;
}
}
vector<int> idx(n);
iota(all(idx), 0ll);
vector<int> ptr_l(n, 0), ptr_r(n, m - 1);
ll score = 0;
for (int ki = 0; ki < k; ki++) {
sort(all(idx), [&] (int i, int j) {
return cnt[i] < cnt[j];
});
for (int i = 0; i < n / 2; i++) {
int j = idx[i];
score -= x[j][ptr_l[j]];
answer[j][ptr_l[j]++] = ki;
}
for (int i = n / 2; i < n; i++) {
int j = idx[i];
score += x[j][ptr_r[j]];
answer[j][ptr_r[j]--] = ki;
}
}
allocate_tickets(answer);
return score;
}
