#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>>());
for(int i = 0; i < n*k; ++i){
if(i < n*k/2){
ans += D[i][0];
C[D[i][1]][0].pb(D[i][2] - (m-k));
}else{
C[D[i][1]][1].pb(D[i][2]);
}
}
for(int i = 0; i < k; ++i){
set<pair<int, int>> S;
for(int i = 0; i < n; ++i){
S.insert({C[i][1].size(), i});
}
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;
}
