#include <bits/stdc++.h>
#include "tickets.h"
using namespace std;
typedef long long ll;
typedef pair <int,int> pii;
ll find_maximum(int k, vector <vector <int>> a)
{
int n = a.size();
int m = a[0].size();
vector <int> PrefixTaken(n, k);
vector <int> SuffixTaken(n, 0);
ll Ans = 0;
for(int i = 0; i < n; i++)
for(int j = 0; j < k; j++)
Ans -= a[i][j];
priority_queue <pair <int,pii>> q;
for(int i = 0; i < n; i++)
q.emplace(a[i][m - 1] + a[i][k - 1], pii(i, m - 1));
for(int repeat = 0; repeat < k * n / 2; repeat++)
{
pair <int,pii> p = q.top();
q.pop();
int x = p.first;
int i = p.second.first;
int j = p.second.second;
int r = m - j + 1;
PrefixTaken[i]--;
SuffixTaken[i]++;
Ans += x;
if(k - r >= 0)
q.emplace(a[i][m - r] + a[i][k - r], pii(i, j - 1));
}
vector <vector <int>> s(n, vector <int> (m, -1));
vector <pii> Sum(k);
for(int j = 0; j < k; j++) Sum[j] = pii(0, j);
for(int i = 0; i < n; i++)
{
for(int j = 0; j < PrefixTaken[i]; j++)
{
Sum[k - j - 1].first--;
s[i][j] = Sum[k - j - 1].second;
}
for(int j = 0; j < SuffixTaken[i]; j++)
{
Sum[j].first++;
s[i][m - j - 1] = Sum[j].second;
}
sort(Sum.begin(), Sum.end());
}
for(int j = 0; j < k; j++)
assert(Sum[j].first == 0);
return allocate_tickets(s), Ans;
}
