#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define all(s) s.begin(),s.end()
#define rall(s) s.rbegin(),s.rend()
ll find_maximum(int k,vector<vector<int>>x){
int n=x.size(),m=x[0].size();
auto s=vector(n,vector<int>(m,-1));
priority_queue<pair<int,int>>p;
ll ans=0;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
if(j<k){
ans-=(ll)x[i][j];
if(j==k-1) p.push({x[i][j]+x[i][j+m-k],i});
}
}
}
vector<int>r(n,k-1);
vector<int>L(n,0),R(n,m-1);
for(int c=0;c<n*k/2;c++){
auto [add,i]=p.top();
ans+=(ll)add;
p.pop();
r[i]--;
if(r[i]>=0) p.push({x[i][r[i]]+x[i][r[i]+m-k],i});
}
vector<pair<int,int>>cnt;
for(int i=0;i<n;i++){
cnt.pb({k-r[i]-1,i});
}
for(int i=0;i<k;i++){
sort(rall(cnt));
for(int j=0;j<n;j++){
if(j<n/2){
s[cnt[j].ss][R[cnt[j].ss]--]=i;
cnt[j].ff--;
}
else{
s[cnt[j].ss][L[cnt[j].ss]++]=i;
}
}
}
allocate_tickets(s);
return ans;
}
