#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#include "tickets.h"
#include <vector>
#define pb push_back
using namespace std;
typedef long long ll;
ll find_maximum(int k, vector<vector<int>> x) {
int n = x.size();
int m = x[0].size();
ll res=0;
vector<vector<int>> answer;
for(int i=0;i<n;i++){
vector<int> d;
for(int j=0;j<m;j++){
d.pb(-1);
}
answer.pb(d);
}
int pre[n],suf[n];
for(int i=0;i<n;i++){
pre[i]=k;
suf[i]=0;
for(int j=0;j<k;j++){
res-=x[i][j];
}
}
set<pair<ll,int>> c;
for(int i=0;i<n;i++){
if(pre[i]==0){
continue;
}
ll val=x[i][m-suf[i]-1]+x[i][pre[i]-1];
c.insert({val,i});
}
for(int i=0;i<k*(n/2);i++){
pair<ll,int> p=*(--c.end());
c.erase(p);
res+=p.first;
int j=p.second;
pre[j]--;
suf[j]++;
if(pre[j]==0){
continue;
}
ll val=x[j][m-suf[j]-1]+x[j][pre[j]-1];
c.insert({val,j});
}
for(int i=0;i<k;i++){
vector<pair<int,int>> d;
for(int j=0;j<n;j++){
d.pb({suf[j],j});
}
sort(d.rbegin(),d.rend());
for(int j=0;j<n/2;j++){
answer[d[j].second][m-d[j].first]=i;
suf[d[j].second]--;
}
for(int j=n/2;j<n;j++){
answer[d[j].second][pre[d[j].second]-1]=i;
pre[d[j].second]--;
}
}
allocate_tickets(answer);
return res;
}
