#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using pii = pair<ll, ll>;
long long find_maximum(signed k, std::vector<std::vector<signed>> x) {
ll n = x.size();
ll m = x[0].size();
vector<vector<signed> > answer(n, vector<signed>(m, -1));
vector<deque<pair<ll, ll> > > nums(n);
for(ll i = 0; i < n; ++i) {
for(ll j = 0; j < m; ++j) {
nums[i].push_back({x[i][j], j});
}
}
ll totalsum = 0;
for(ll round = 0; round < k; ++round) {
vector<pii> sums(n);
for(ll i = 0; i < n; ++i) {
sums[i] = {nums[i].front().first + nums[i].back().first, i};
}
sort(sums.begin(), sums.end());
for(ll i = 0; i < n/2; ++i) {
const ll idx1 = sums[i].second;
const ll idx2 = nums[idx1].front().second;
totalsum -= nums[idx1].front().first;
answer[idx1][idx2] = round;
nums[idx1].pop_front();
}
for(ll i = n/2; i < n; ++i) {
const ll idx1 = sums[i].second;
const ll idx2 = nums[idx1].back().second;
totalsum += nums[idx1].back().first;
answer[idx1][idx2] = round;
nums[idx1].pop_back();
}
}
allocate_tickets(answer);
return totalsum;
}
/*
4 2 1
5 9
1 4
3 6
2 7
2 3 2
0 2 5
1 1 3
*/
