#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ar array
long long find_maximum(int k, vector<vector<int>> x) {
int n=x.size();
int m=x[0].size();
ll winnings=0;
vector<ar<int, 2>> gain;
for (int i=0; i<n; i++)
for (int j=0; j<k; ++j) {
gain.push_back({x[i][j]+x[i][m-k+j], i});
winnings-=x[i][j];
}
sort(gain.rbegin(), gain.rend());
vector<int> cnt(n);
for (int i=0; i<n*k/2; ++i) {
winnings+=gain[i][0];
++cnt[gain[i][1]];
}
vector<vector<int>> ans(n, vector<int>(m, -1));
for (int r=0; r<k; ++r) {
vector<ar<int, 2>> v(n);
for (int i=0; i<n; ++i)
v[i]={cnt[i], i};
sort(v.begin(), v.end());
for (int i=0; i<n/2; ++i) {
int ind=v[i][1];
int lft=k-r-cnt[ind];
assert(lft>0);
ans[ind][lft-1]=r;
}
for (int i=n/2; i<n; ++i) {
int ind=v[i][1];
int lft=cnt[ind];
assert(lft>0);
ans[ind][m-lft]=r;
--cnt[ind];
}
}
allocate_tickets(ans);
return winnings;
}
