#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define f1 first
#define s2 second
using ii = pair<int, int>;
using ll = long long;
ll find_maximum(int K, vector<vector<int>> V)
{
int N = (int)V.size(), M = (int)V[0].size();
vector<vector<ii>> vec(N, vector<ii>(M));
for (int i = 0; i < N; ++i)
for (int j = 0; j < M; ++j)
vec[i][j] = {V[i][j], j};
for (int i = 0; i < N; ++i)
sort(vec[i].begin(), vec[i].end());
ll S = 0;
vector<vector<int>> ans(N, vector<int> (M, -1));
priority_queue<ii> pq;
vector<bool> used(N, false);
for (int i = 0; i < K; ++i)
{
while (!pq.empty())
pq.pop();
if (i+1 == M)
{
ll sum = 0;
for (int j = 0; j < N; ++j)
{
sum += vec[j][0].f1;
pq.push({-2*vec[j][0].f1, 69});
ans[j][vec[j][0].s2] = i;
}
for (int j = 0; j < N/2; ++j)
sum += pq.top().f1, pq.pop();
S += sum;
}
else
{
fill(used.begin(), used.end(), false);
ll sum = 0;
for (int j = 0; j < N; ++j)
{
sum += vec[j].back().f1;
pq.push({-vec[j][0].f1 - vec[j].back().f1, j});
}
for (int j = 0; j < N/2; ++j)
{
sum += pq.top().f1;
used[pq.top().s2] = true;
pq.pop();
}
for (int j = 0; j < N; ++j)
{
if (used[j])
{
ans[j][vec[j][0].s2] = i;
vec[j].erase(vec[j].begin());
}
else
{
ans[j][vec[j].back().s2] = i;
vec[j].pop_back();
}
}
S += sum;
}
}
allocate_tickets(ans);
return S;
}
