#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<array<ll, 3> > v(n*m);
for(ll i = 0; i < n; ++i) {
for(ll j = 0; j < m; ++j) {
v[m*i + j] = {x[i][j], i, j};
}
}
vector<ll> mins(n, 0), maxes(n, k-1);
sort(v.begin(), v.end());
ll total = 0;
for(ll idx = 0; idx < n*m/2; ++idx) {
auto [val, i, j] = v[idx];
total -= val;
answer[i][j] = mins[i];
mins[i]++;
}
for(ll idx = n*m/2; idx < n*m; ++idx) {
auto [val, i, j] = v[idx];
total -= val;
answer[i][j] = maxes[i];
maxes[i]++;
}
allocate_tickets(answer);
return total;
}
/*
4 2 1
5 9
1 4
3 6
2 7
2 3 2
0 2 5
1 1 3
*/
