#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
long long find_maximum(int k, vector<vector<int>> v ) {
int n = v.size(), m = v[0].size();
vector<set<int>> smax(n), smin(n);
ll resp = 0;
vector<tuple<ll, int, int, int>> ordem;
for( int i = 0; i < n; i++ ){
for( int j = 0; j < k; j++ ){
ordem.emplace_back( -v[i][j] - v[i][m - k + j], i, j, m - k + j );
smax[i].insert(m - k + j);
resp += v[i][m - k + j];
}
}
sort( ordem.rbegin(), ordem.rend() );
for( int t = 0; t < n*k/2; t++ ){
auto [val, i, j1, j2] = ordem[t];
resp += val;
smax[i].erase(j2);
smin[i].insert(j1);
}
vector<vector<int>> tickets( n, vector<int>(m, -1));
vector<int> round(n);
iota(round.begin(), round.end(), 0);
for( int t = 0; t < k; t++ ){
sort( round.begin(), round.end(), [&]( int a, int b ){
return smax[a].size() < smax[b].size();
});
for( int i = 0; i < n/2; i++ ){
tickets[round[i]][*smin[round[i]].begin()] = t;
smin[round[i]].erase(smin[round[i]].begin());
}
for( int i = n/2; i < n; i++ ){
tickets[round[i]][*smax[round[i]].begin()] = t;
smax[round[i]].erase(smax[round[i]].begin());
}
}
allocate_tickets(tickets);
return resp;
}
