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