#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;
idata L(N, 0);
idata R(N, M - 1);
int result = 0;
vector<vector<signed>> allocations(N, vector<signed>(M, -1));
for (int k = 0; k < K; k ++) {
int lcr = 0;
vd compos;
for (int i = 0; i < N; i ++) {
lcr -= x[i][L[i]];
compos.push_back({
x[i][R[i]] + x[i][L[i]],
i
});
allocations[i][L[i]] = k;
L[i] ++;
}
sort(compos.rbegin(), compos.rend());
for (int iC = 0; iC < H; iC ++) {
lcr += compos[iC].first;
int iV = compos[iC].second;
L[iV] --;
allocations[iV][L[iV]] = - 1;
allocations[iV][R[iV]] = k;
R[iV] --;
}
result += lcr;
}
allocate_tickets(allocations);
return result;
}
