#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
using pi = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
using vl = vector<ll>;
using vvl = vector<vl>;
#define bg(x) (x).begin()
#define en(x) (x).end()
#define all(x) bg(x), en(x)
const ll INF = 4e18;
ll find_maximum(int k, vvi x) {
int n = x.size(), m = x[0].size(), h = x.size() / 2;
vvi answer(n, vi(m, -1));
ll ans = 0;
// vvl dp(n+1, vl(k*(n+1), -INF)); vvi par(n+1, vi(k*(n+1), -1));
// dp[0][k*h] = 0;
// for (int i = 1; i <= n; i++) {
// vl pref(m+1, 0LL); for (int j = 0; j < m; j++) pref[j+1] += pref[j] + x[i-1][j];
// for (int j = 0; j <= k*n; j++) {
// for (int neg = 0; neg <= k; neg++) {
// ll ovr = k - 2*neg, s = pref[neg], b = pref[m] - pref[m-k+neg];
// if (j - ovr < 0 || j - ovr > k*n) continue;
// if (dp[i-1][j-ovr] != -INF && dp[i-1][j-ovr] + b - s >= dp[i][j]) dp[i][j] = dp[i-1][j-ovr] + b - s, par[i][j] = neg;
// }
// }
// }
// for (int j = 0; j <= k*n; j++) {
// for (int i = 0; i <= n; i++) {
// if (dp[i][j] != -INF) cerr << setw(3) << dp[i][j] << " ";
// else cerr << "-∞ ";
// }
// cerr << "\n";
// }
// int st = k*h;
vi c(n, 0); vl si(n, 0);
for (int i = 0; i < n; i++) {
c[i] = k; for (int j = 0; j < k; j++) si[i] -= x[i][j];
ans += si[i];
}
for (int i = 0; i < n*k / 2; i++) {
ll best = -1, bc = -INF;
for (int j = 0; j < n; j++) {
if (c[j] == 0) continue;
ll vc = x[j][c[j]-1] + x[j][m-k+c[j]-1];
if (best == -1 || vc > bc) best = j, bc = vc;
}
ans += bc; c[best]--;
}
// for (int i = n; i >= 1; i--) {
// ll neg = par[i][st];
// c[i-1] = neg;
// ll ovr = k - 2*neg;
// st -= ovr;
// }
set<pi> pq; for (int i = 0; i < k; i++) pq.insert({h, i});
for (int i = 0; i < n; i++) {
set<int> nope; vector<pi> q2;
for (int j = 0; j < c[i]; j++) {
auto f = *pq.rbegin(); pq.erase(f);
q2.push_back(f); q2.back().first--;
nope.insert(f.second); answer[i][j] = f.second;
}
int t = 0;
for (int j = m-1; j >= m-(k-c[i]); j--) {
while (nope.count(t)) t++;
answer[i][j] = t++;
}
for (auto f : q2) {
pq.insert(f);
}
}
// ans += dp[n][k*h];
allocate_tickets(answer);
return ans;
}
