#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
long long find_maximum(int k, vector<vector<int>> x) {
int n = x.size();
int m = x[0].size();
vector<vector<pair<ll, int>>> a(n, vector<pair<ll, int>>(m));
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) a[i][j] = {x[i][j], j};
}
ll ans = 0;
vector<pair<int, int>> v(n);
vector<int> s_cnt(n);
priority_queue<pair<ll, int>> pq;
for (int i = 0; i < n; i++) {
v[i] = {k-1, m-1};
pq.push({x[i][k-1]+x[i][m-1], i});
for (int j = 0; j < k; j++) {
ans -= x[i][j];
s_cnt[i]++;
}
}
int l = 0;
int targ = n/2*k;
vector<int> l_cnt(n);
while (l < targ) {
auto [add, i] = pq.top();
pq.pop();
ans += add;
s_cnt[i]--;
l_cnt[i]++;
l++;
swap(a[i][v[i].first], a[i][v[i].second]);
v[i].first--, v[i].second--;
if (v[i].second < k && k < m) v[i].second = m-1;
if (v[i].first >= 0) pq.push({a[i][v[i].first].first+a[i][v[i].second].first, i});
}
vector<int> l_ptr(n), r_ptr(n, k-1);
vector<vector<int>> answer(n, vector<int>(m, -1));
for (int i = 0; i < k; i++) {
int small = 0, large = 0;
vector<int> p;
for (int j = 0; j < n; j++) {
if (s_cnt[j] == 0) {
answer[j][a[j][r_ptr[j]].second] = i;
r_ptr[j]--;
l_cnt[j]--;
large++;
}
else if (l_cnt[j] == 0) {
answer[j][a[j][l_ptr[j]].second] = i;
l_ptr[j]++;
s_cnt[j]--;
small++;
}
else p.push_back(j);
}
for (auto j : p) {
if (small < n/2) {
answer[j][a[j][l_ptr[j]].second] = i;
l_ptr[j]++;
s_cnt[j]--;
small++;
}
else {
answer[j][a[j][r_ptr[j]].second] = i;
r_ptr[j]--;
l_cnt[j]--;
large++;
}
}
}
allocate_tickets(answer);
return ans;
}
