#include <bits/stdc++.h>
#include <tickets.h>
using namespace std;
using ll = long long;
ll find_maximum(int k, vector<vector<int>> x) {
int n = x.size(), m = x[0].size();
ll ans = 0;
vector<int> pos(n, k - 1);
vector<vector<int>> sol(n, vector<int>(m, -1));
priority_queue<pair<int, int>> PQ;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < k; ++j)
ans -= x[i][j];
PQ.emplace(x[i][k - 1] + x[i][m - 1], i);
}
for (int i = 0; i < n * k / 2; ++i) {
auto [s, j] = PQ.top();
PQ.pop();
ans += s;
if (--pos[j] >= 0)
PQ.emplace(x[j][pos[j]] + x[j][m - k + pos[j]], j);
}
for (int i = 0, l = 0, r = k - 1; i < n; ++i) {
for (int j = 0; j <= pos[i]; ++j)
sol[i][j] = l, l = (l + 1) % k;
for (int j = m - 1; j > m - k + pos[i]; --j)
sol[i][j] = r, r = (r - 1 + k) % k;
}
allocate_tickets(sol);
return ans;
}
