#include "tickets.h"
#include <bits/stdc++.h>
#define int long long
using namespace std;
using idata = vector<int>;
using igrid = vector<idata>;
using di = pair<int, int>;
using vd = vector<di>;
int find_maximum(signed K, vector<vector<signed>> x) {
int N = x.size(); int M = x[0].size(); int H = N >> 1;
int result = 0;
for (int i = 0; i < N; i ++)
for (int k = 1; k <= K; k ++)
result += x[i][M - k];
priority_queue<di> deltas;
idata R(N, M - K);
for (int i = 0; i < N; i ++)
deltas.push({ - x[i][0] - x[i][M - K], i });
for (int i = 0; i < H * K; i ++) {
di curr = deltas.top(); deltas.pop();
int j = curr.second;
result += curr.first;
R[j] ++;
if (R[j] == M) continue ;
int al = R[j] - (M - K);
deltas.push({ - x[j][al] - x[j][R[j]], j });
}
vector<vector<signed>> allocations(N, vector<signed>(M, -1));
idata L(N, 0);
for (int k = 0; k < K; k ++) {
vd RV;
for (int i = 0; i < N; i ++)
RV.push_back({ R[i], i });
sort(RV.rbegin(), RV.rend());
for (int i = 0; i < H; i ++) {
int e = RV[i].second;
allocations[e][L[e]] = k;
L[e] ++;
}
for (int i = H; i < N; i ++) {
int e = RV[i].second;
allocations[e][R[e]] = k;
R[e] ++;
}
}
allocate_tickets(allocations);
return result;
}
