#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<int, int>;
#define X first
#define Y second
ll find_maximum(int k, vector<vector<int>> a) {
int n = a.size(), m = a[0].size();
vector<vector<int>> ord(n, vector<int>(m));
ll ans = 0;
vector<int> cnt(n, 0);
priority_queue<pii> pq;
for(int i=0; i<n; i++) {
iota(ord[i].begin(), ord[i].end(), 0);
sort(ord[i].begin(), ord[i].end(), [&](int x, int y) {
return a[i][x] < a[i][y];
});
for(int j=0; j<k; j++) ans -= a[i][ord[i][j]];
pq.push({a[i][ord[i][m-1]]+a[i][ord[i][k-1]], i});
}
for(int t=0; t<n*k/2; t++) {
pii d = pq.top();
pq.pop();
ans += d.X;
if((++cnt[d.Y])<k)
pq.push({a[d.Y][ord[d.Y][m-1-cnt[d.Y]]]+a[d.Y][ord[d.Y][k-1-cnt[d.Y]]], d.Y});
}
vector<int> L(n, 0), R(n, m-1);
vector<vector<int>> b(n, vector<int>(m, -1));
for(int r=0; r<k; r++) {
int ct=0;
vector<bool> mark(n, 0);
for(int i=0; i<n; i++)
if(cnt[i]==k-r) {
b[i][ord[i][R[i]--]] = r;
cnt[i]--;
mark[i] = 1;
ct++;
}
for(int i=0; i<n && ct<n/2; i++)
if(!mark[i] && cnt[i]) {
b[i][ord[i][R[i]--]] = r;
cnt[i]--;
mark[i] = 1;
ct++;
}
for(int i=0; i<n; i++)
if(!mark[i])
b[i][ord[i][L[i]++]] = r;
}
allocate_tickets(b);
return ans;
}
