#include "tickets.h"
#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define pb push_back
#define vi vector<int>
#define all(x) x.begin(),x.end()
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n = x.size();
int m = x[0].size();
std::vector<std::vector<int>> answer(n, vector<int>(m, -1));
vector<array<int, 3>> D;
vector<vector<vector<int>>> C(n, vector<vector<int>>(2));
ll ans = 0;
for(int i = 0; i < n; ++i) for(int j = m - k; j < m; ++j) {
ans += x[i][j];
D.pb({-(x[i][j] + x[i][j - (m-k)]), i, j});
}
sort(all(D), greater<array<int,3>>());
int co = 0;
for(int i = 0; i < n*k; ++i){
if(co < n*k/2 && answer[D[i][1]][D[i][2] - (m-k)] == -1){
ans += D[i][0];
C[D[i][1]][0].pb(D[i][2] - (m-k));
answer[D[i][1]][D[i][2] - (m-k)] = 1;
++co;
}else{
C[D[i][1]][1].pb(D[i][2]);
answer[D[i][1]][D[i][2]] = 1;
}
}
for(int i = 0; i < n; ++i) sort(all(C[i][0])), sort(all(C[i][1]), greater<int>());
for(int i = 0; i < k; ++i){
set<pair<int, int>> S;
for(int j = 0; j < n; ++j){
assert(C[j][0].size() || C[j][1].size());
S.insert({C[j][1].size(), j});
}
int cur = 0;
auto it = S.begin();
vector<ll> tot;
while(it != S.end()){
int v = (*it).second;
if((cur < n/2 && C[v][0].size()) || (cur >= n/2 && C[v][1].size() == 0)){
answer[v][C[v][0].back()] = i;
C[v][0].pop_back();
}else{
answer[v][C[v][1].back()] = i;
C[v][1].pop_back();
}
++cur;
it = next(it);
}
// cout << "f" << endl;
}
allocate_tickets(answer);
return ans;
}
