#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) {
cnt--;
sub[v[i].second]++;
tot+=v[i].first;
}
}
while(true&&k<m){
int mn=1e12;
int mx=-1e12;
int mxI=-1;
int mnI=-1;
for (int i = 0; i < n; i++)
{
int vx=-1e12;
int vn=1e12;
if(last[i]>0) vx=x[i][last[i]-1]+x[i][m-(k-last[i])-1];
if(last[i]!=k) vn=(x[i][last[i]]+x[i][m-(k-last[i])]);
if(vx>mx){
mxI=i;
mx=vx;
}
if(vn<mn){
mnI=i;
mn=vn;
}
}
if(mx-mn>0) {
tot+=mx-mn;
last[mxI]--;
last[mnI]++;
}else {
break;
}
}
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 = 0; i<n; 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;
}
