#include "tickets.h"
#include <bits/stdc++.h>
#define int long long
#define pii pair<int,int>
#define ff first
#define ss second
using namespace std;
long long find_maximum(signed k, vector<vector<signed>> v) {
int n = v.size();
int m = v[0].size();
for(auto&vec:v)
sort(vec.begin(),vec.end());
vector<vector<signed>> answer(n,vector<signed>(m,-1));
vector<int> plus(n,0);
int ans = 0;
priority_queue<pii> pq;
for(int i = 0; i < n; i++)
for(int j = 0; j+m-k < m; j++)
pq.push({v[i][j]+v[i][j+m-k],i}),ans+=-v[i][j];
{
int cnt = 0;
while (cnt < n * k / 2)
{
pii x = pq.top();
pq.pop();
cnt++;
plus[x.ss]++;
ans += x.ff;
}
}
vector<int> sz(k,0);
set<int> free;
for(int i = 0; i < k; i++)
free.insert(i);
vector<set<int>> has(k);
for(int i = 0; i< n; i++)
{
int j = 0;
vector<int> iter;
for(int x : free)
iter.push_back(x);
sort(iter.begin(),iter.end(),[&](int a,int b){return sz[a]<sz[b];});
for(int x : iter)
{
if(j >= k-plus[i])
break;
answer[i][j] = x;
sz[x]++;
has[x].insert(i);
j++;
}
set<int> neu;
for(int x :free)
if(sz[x]<n/2)
neu.insert(x);
free = neu;
}
for(int i = 0; i < k; i++)
free.insert(i);
for(int i = 0; i< n; i++)
{
int j = m-plus[i];
vector<int> iter;
for(int x : free)
iter.push_back(x);
sort(iter.begin(),iter.end(),[&](int a,int b){return sz[a]<sz[b];});
for(int x : iter)
{
if(has[x].count(i))continue;
if(j>=m)
break;
answer[i][j] = x;
sz[x]++;
j++;
}
set<int> neu;
for(int x :free)
if(sz[x]<n)
neu.insert(x);
free = neu;
}
allocate_tickets(answer);
return ans;
}
