#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();
ll sum = 0;
vector<vector<int>> ans(N, vector<int> (M, -1));
vector<ii> vec;
vector<int> lt(N, 0), rt(N, K);
for (int i = 0; i < N; ++i)
{
for (int j = M-K; j < M; ++j)
{
sum += V[i][j];
vec.pb({-V[i][j] - V[i][j - (M-K)], i});
}
}
sort(vec.rbegin(), vec.rend());
for (int i = 0; i < N*K/2; ++i)
sum += vec[i].f1, lt[vec[i].s2]++, rt[vec[i].s2]--;
vector<vector<bool>> used(N, vector<bool>(K, false));
for (int i = 0, ctr = 0; i < N; ++i)
{
for (int j = 0; j < lt[i]; ++j)
{
ans[i][j] = ctr; used[i][ctr] = true;
ctr = (ctr + 1) % K;
}
}
for (int i = 0; i < N; ++i)
{
for (int j = M - rt[i], k = 0; j < M; ++j)
{
while (used[i][k]) ++k;
ans[i][j] = k++;
}
}
allocate_tickets(ans);
return sum;
}
