#include "tickets.h"
#include<bits/stdc++.h>
#define int long long
#define pb push_back
#define mp make_pair
#define f0r(i,n) for(int i = 0; i<n; i++)
#define FOR(i, k, n) for(int i = k; i<n; i++)
#define vi vector<long long>
#define vvi vector<vi>
#define pii pair<int,int>
#define vpii vector<pii>
#define vb vector<bool>
#define vout(v) for(auto u : v)cout<<u<<' '; cout<<'\n';
#define dout(x) cout<<x<<' '<<#x<<'\n';
using namespace std;
long long find_maximum(signed k, std::vector<std::vector<signed>> x) {
int n = x.size(); int m = x[0].size(); vector<vector<signed>> ans(n, vector<signed>(m,-1));
vector<vpii> w(n,vpii(m)); f0r(i,n)f0r(j,m)w[i][j] = mp(x[i][j], j); f0r(i,n){sort(w[i].begin(),w[i].end());}
vvi v(n,vi(m)),d(n,vi(m)); f0r(i,n)f0r(j,m)v[i][j]=w[i][j].first,d[i][j]=w[i][j].second;
vi plus(n); vpii ord; f0r(i,n){
int b = m-1, a = k-1; f0r(j,k){
ord.pb(mp(v[i][a] + v[i][b], i)); b--; a--;
}
} sort(ord.rbegin(), ord.rend());
f0r(i,n*k/2)plus[ord[i].second]++; //suffix length is plus
int val = 0; f0r(i,n){f0r(j,k-plus[i])val-=v[i][j]; for(int j = m-1; j >= m-plus[i]; j--)val+=v[i][j];}
vvi good(n), bad(n); f0r(i,n){f0r(j,k-plus[i])bad[i].pb(d[i][j]); for(int j = m-1; j >= m-plus[i]; j--)good[i].pb(d[i][j]);}
f0r(tt,k){
vb vis(n); int g = n/2, b = n/2;
f0r(i,n){
if(good[i].empty())b--, ans[i][bad[i].back()] = tt, bad[i].pop_back(),vis[i]=1;
else if(bad[i].empty())g--, ans[i][good[i].back()]=tt,good[i].pop_back(),vis[i]=1;
}
f0r(i,n)if(!vis[i]){
if(g>0)g--,ans[i][good[i].back()]=tt,good[i].pop_back();
else b--,ans[i][bad[i].back()] = tt, bad[i].pop_back();
}
}
allocate_tickets(ans); return val;
}
