#include "tickets.h"
#include <bits/stdc++.h>
using ll = long long;
using namespace std;
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n = x.size();
int m = x[0].size();
vector<int> cnt(n, 0);
ll cur = 0;
for(int i = 0; i < n; i++) {
for(int j = m-k; j < m; j++) {
cur += x[i][j];
}
}
auto cost = [&](int id, int lvl) {
if(lvl == k) return -(1ll<<60);
return ll(-x[id][lvl] -x[id][m-k+lvl]);
};
priority_queue<pair<ll, int>> a;
for(int i = 0; i < n; i++) a.push({cost(i, 0), i});
int need = n*k/2;
while(need--) {
auto [cst, i] = a.top();
a.pop();
cur += cst;
a.push({cost(i, ++cnt[i]), i});
}
vector<vector<int>> res(n, vector<int>(m, -1));
vector<int> ol;
for(int lp = 0, rp = 0, i = 0; i < n; i++) {
for(int j = 0; j < cnt[i]; j++) {
res[i][j] = lp;
lp = (lp+1)%k;
}
rp = lp;
for(int j = m-k+cnt[i]; j < m; j++) {
res[i][j] = rp;
rp = (rp+1)%k;
}
}
allocate_tickets(res);
return cur;
}
