#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
const int MAX=1e9;
long long find_maximum(signed __k, std::vector<std::vector<signed>> x) {
int n=sz(x);
int m=sz(x[0]);
int k=__k;
vector<pair<int,int>> v;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++) v.push_back({x[i][j], i});
}
sort(all(v));
int cnt=0;
int l=0;
vector<int> sub(n);
vector<int> last(n,0);
int tot=0;
while(cnt<(n/2)*k){
if(sub[v[l].second]<k) {
last[v[l].second]++;
sub[v[l].second]++;
cnt++;
tot-=v[l].first;
}
l++;
}
for (int i=sz(v)-1; i>=0; i--)
{
if(sub[v[i].second]<k) {
sub[v[i].second]++;
tot+=v[i].first;
}
}
vector<vector<signed>> ret(n,vector<signed>(m,-1));
set<pair<int,int>> st;
vector<int> stv(k,0);
for (int i = 0; i < k; i++) st.insert({stv[i],i});
for (int i = n-1; i>=0; i--)
{
vector<pair<int,int>> ins;
for (int j = 0; j < last[i]; j++) {
int v=(*st.rbegin()).second;
st.erase(*st.rbegin());
stv[v]--;
ins.push_back({stv[v],v});
ret[i][j]=v;
}
for (int j = m-(k-last[i]); j < m; j++) {
int v=(*st.begin()).second;
st.erase(*st.begin());
stv[v]++;
ins.push_back({stv[v],v});
ret[i][j]=v;
}
for (int j = 0; j < k; j++) st.insert(ins[j]);
}
allocate_tickets(ret);
return tot;
}
