#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
void allocate_tickets( std::vector<std::vector<int>> _d);
ll find_maximum(int k, vector<vector<int>> x) {
ll n = x.size(), m = x[0].size();
vector<vector<pll>> x2(n, vector<pll>(m));
for (ll i=0; i<n; i++) {
for (ll j=0; j<m; j++) {
x2[i][j] = {x[i][j], j};
}
sort(x2[i].begin(), x2[i].end());
}
ll sum = 0;
vector<ll> cnt(n, k);
priority_queue<pll> pq;
for (ll i=0; i<n; i++) {
for (ll j=0; j<k; j++) {
sum -= x2[i][j].first;
}
pq.push({x2[i][k-1].first + x2[i].back().first, i});
}
for (ll rep=0; rep<n/2*k; rep++) {
sum += pq.top().first;
ll i = pq.top().second;
pq.pop();
cnt[i] --;
if (cnt[i] > 0) {
pq.push({x2[i][cnt[i]].first + x2[i][m-k+cnt[i]-1].first, i});
}
}
vector<vector<int>> ans(n, vector<int>(m, -1));
for (ll rep=0; rep<k; rep++) {
vector<ll> id(n);
iota(id.begin(), id.end(), 0);
sort(id.begin(), id.end(), [&] (ll &u, ll &v) { return cnt[u] > cnt[v]; });
for (ll j=0; j<n/2; j++) {
ll i = id[j];
ans[i][x2[i][cnt[i]-1].second] = rep;
cnt[i] --;
}
for (ll j=n/2; j<n; j++) {
ll i = id[j];
ans[i][x2[i][m-(k-rep-cnt[i])].second] = rep;
}
}
allocate_tickets(ans);
return sum;
}
