#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define all(x) x.begin(), x.end()
long long find_maximum(int k, vector<vector<int>> x) {
int n = x.size();
int m = x[0].size();
vector<vector<int>> answer(n, vector<int>(m, -1));
vector<array<int, 3>> arr(n * m);
k = min(k, m);
for (int i = 0; i < n * m; i++){
arr[i][0] = x[i / m][i % m];
arr[i][1] = i / m;
arr[i][2] = i % m;
}
sort(all(arr));
vector<vector<array<int, 5>>> mainarray(n, vector<array<int, 5>>(k));
vector<int> indd(n);
int ort = arr[arr.size() / 2][0];
for (int i = 0; i < arr.size(); i++){
if (indd[arr[i][1]] < k){
mainarray[arr[i][1]][indd[arr[i][1]]][0] = ort - arr[i][0];
mainarray[arr[i][1]][indd[arr[i][1]]][1] = arr[i][1];
mainarray[arr[i][1]][indd[arr[i][1]]][2] = arr[i][2];
indd[arr[i][1]]++;
}
}
for (int i = arr.size() - 1; i >= 0; i--){
if (indd[arr[i][1]] > 0){
indd[arr[i][1]]--;
mainarray[arr[i][1]][indd[arr[i][1]]][0] -= arr[i][0] - ort;
mainarray[arr[i][1]][indd[arr[i][1]]][3] = arr[i][1];
mainarray[arr[i][1]][indd[arr[i][1]]][4] = arr[i][2];
}
}
priority_queue<array<int, 2>> pque;
for (int i = 0; i < n; i++){
pque.push({ mainarray[i][0][0], i });
}
for (int i = 0; i < n * k / 2; i++){
auto f = pque.top();
pque.pop();
indd[f[1]]++;
if (indd[f[1]] < k){
pque.push({ mainarray[f[1]][indd[f[1]]][0], f[1] });
}
}
vector<array<int, 2>> lft, rgt;
long long ret = 0;
for (int i = 0; i < n; i++){
for (int j = 0; j < indd[i]; j++){
ret -= x[mainarray[i][j][1]][mainarray[i][j][2]];
lft.push_back({ mainarray[i][j][1], mainarray[i][j][2] });
}
for (int j = indd[i]; j < k; j++){
ret += x[mainarray[i][j][3]][mainarray[i][j][4]];
rgt.push_back({ mainarray[i][j][3], mainarray[i][j][4] });
}
}
for (int i = 0; i < rgt.size(); i++){
answer[rgt[i][0]][rgt[i][1]] = i % k;
}
for (int i = 0; i < lft.size(); i++){
answer[lft[i][0]][lft[i][1]] = i % k;
}
allocate_tickets(answer);
return ret;
}
