#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef vector<int> vi;
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define mk make_pair
#define pb push_back
#define fr first
#define sc second
vi apear, ord;
ll find_maximum(int k, vector<vi> x) {
int n = sz(x), m = sz(x[0]);
vi qtd(n);
ll TOT = 0;
priority_queue<pii> sub, add;
for(int i = 0; i < n/2; i++) {
for(int j = 0; j < k; j++)
TOT -= x[i][j];
qtd[i] = k;
sub.push({x[i][m-1] + x[i][k-1], i});
}
for(int i = n/2; i < n; i++) {
for(int j = m-k; j < m; j++)
TOT += x[i][j];
add.push({- x[i][m-k] - x[i][0], i});
}
while(sz(add) and sz(sub)) {
auto [cost_i, i] = add.top();
auto [cost_j, j] = sub.top();
add.pop(); sub.pop();
if(cost_i + cost_j <= 0) break;
TOT += cost_i + cost_j;
qtd[i]++;
qtd[j]--;
if(qtd[i] < k) add.push({- x[i][qtd[i]] - x[i][m-k+qtd[i]], i});
if(qtd[j] > 0) sub.push({x[j][qtd[j]-1] + x[j][m-k+qtd[j]-1], j});
}
vector<vi> ans(n, vi(m, -1));
apear.resize(k);
ord.resize(k);
for(int o = 0; o < k; o++) ord[o] = o;
for(int i = 0; i < n; i++) {
sort(all(ord), [](int a, int b){
return mk(apear[a], a) > mk(apear[b], b);
});
for(int j = 0; j < qtd[i]; j++)
ans[i][j] = ord[j], apear[ord[j]]--;
for(int j = m-k+qtd[i]; j < m; j++)
ans[i][j] = ord[j-m+k], apear[ord[j-m+k]]++;
}
allocate_tickets(ans);
return TOT;
}
