#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define loop(x, i) for (int i = 0; i < (x); i++)
#define ALL(x) (x).begin(), x.end()
#define pb push_back
#define int long long
typedef pair<int, int> ii;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<signed> vi32;
typedef vector<bool> vb;
typedef set<int> si;
typedef vector<vi> vvi;
typedef vector<vi32> vvi32;
typedef vector<si> vsi;
typedef vector<ii> vii;
typedef set<iii> siii;
int find_maximum(signed k, vvi32 x)
{
int n = x.size();
int m = x[0].size();
vvi32 answer(n, vi32(m, -1));
vi firstFree(n, k), lastFree(n, m - 1);
priority_queue<ii> switches;
loop(n, i)
{
switches.push({x[i][firstFree[i] - 1] + x[i][lastFree[i]], i});
}
loop(k * n / 2, iter)
{
if (switches.empty())
break;
auto [v, i] = switches.top();
switches.pop();
firstFree[i]--;
lastFree[i]--;
if (firstFree[i] > 0)
switches.push({x[i][firstFree[i] - 1] + x[i][lastFree[i]], i});
}
int res = 0;
loop(k, round)
{
vi a;
vii plusPerPile;
loop(n, i)
{
plusPerPile.pb({m - 1 - lastFree[i], i});
}
sort(ALL(plusPerPile));
for (int ix = 0; ix < n; ix++)
{
auto &[cnt, i] = plusPerPile[ix];
if (ix >= n / 2)
{
lastFree[i]++;
answer[i][lastFree[i]] = round;
a.pb(x[i][lastFree[i]]);
}
else
{
firstFree[i]--;
answer[i][firstFree[i]] = round;
a.pb(x[i][firstFree[i]]);
}
}
sort(ALL(a));
int b = a[n / 2];
for (int v : a)
res += abs(v - b);
}
allocate_tickets(answer);
return res;
}
