#include "tickets.h"
#include <bits/stdc++.h>
using std::cin;
using std::cout;
using std::endl;
using std::vector;
using std::string;
using ll = long long;
using vi = vector<ll>;
using vii = vector<vi>;
using pii = std::pair<ll,ll>;
#define ln "\n"
#define rep(i,j,k) for(ll i=ll(j); i<ll(k); i++)
#define REP(i,j,k) for(ll i=ll(j); i<=ll(k); i++)
#define per(i,j,k) for(ll i=ll(j); i>=ll(k); i--)
#define pb emplace_back
#define mp std::make_pair
#define mtp std::make_tuple
#define all(a) a.begin(),a.end()
constexpr ll inf = (1ll<<60);
long long find_maximum(int k, std::vector<std::vector<int>> x) {
ll N = x.size();
ll M = x[0].size();
vector<vector<int>> ans_allocate(N,vector<int>(M,-1));
ll final_ans = -inf;
REP(half,0,N*M){
vector<std::tuple<ll,ll,ll>> data;
rep(i,0,N){
rep(j,0,M) data.pb(mtp(x[i][j],i,j));
}
sort(all(data));
ll ans = 0;
vii left(N), right(N);
rep(i,0,half){
ll val, I,J; std::tie(val, I,J) = data[i];
left[I].pb(J);
}
rep(i,half,N*M){
ll val, I,J; std::tie(val, I,J) = data[i];
right[I].pb(J);
}
vii use_left(N), use_right(N);
ll goal = N*k/2;
ll current = 0;
std::priority_queue<pii> que;
rep(i,0,N){
rep(j,left[i].size(),k){
use_right[i].pb(right[i].back());
right[i].pop_back();
current++;
}
while(left[i].size() > k) left[i].pop_back();
if(right[i].empty() || left[i].empty()) continue;
que.push(mp(x[i][right[i].back()]+x[i][left[i].back()], i));
}
/*rep(i,0,N){
cout << "! " << i << ln;
for(auto el: left[i]) cout << el << " ";
cout << ln;
for(auto el: use_right[i]) cout << el << " ";
cout << ln;
}*/
while(current < goal){
if(que.empty()) break;
auto el = que.top(); que.pop();
ll i = el.second;
left[i].pop_back();
use_right[i].pb(right[i].back());
right[i].pop_back();
current++;
if(right[i].empty() || left[i].empty()) continue;
que.push(mp(x[i][right[i].back()]+x[i][left[i].back()], i));
}
if(current != goal) continue;
use_left = left;
vector<vector<int>> allocate(N,vector<int>(M,-1));
vector<pii> cnt(k);
rep(i,0,k) cnt[i] = mp(0,i);
rep(i,0,N){
sort(all(cnt));
ll idx = 0;
for(auto el: use_left[i]){
allocate[i][el] = cnt[idx].second;
cnt[idx].first++;
idx++;
//cout << x[i][el] << " ";
ans -= x[i][el];
}
for(auto el: use_right[i]){
allocate[i][el] = cnt[idx].second;
cnt[idx].first--;
idx++;
ans += x[i][el];
//cout << " " << x[i][el];
}
//cout << ln;
}
//cout << ans << ln;
if(ans > final_ans){
final_ans = ans;
ans_allocate = allocate;
}
}
allocate_tickets(ans_allocate);
return final_ans;
}
