#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> ans;
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n = x.size();
int m = x[0].size();
ans = vector<vector<int>>(n, vector<int>(m, -1));
long long res = 0;
for (int r = 0; r < k; r++) {
set<pair<int, int>> low, high;
vector<pair<int, int>> a(n);
for (int i = 0; i < n; i++) {
int mn = -1;
int mx = -1;
for (int j = 0; j < m; j++)
if (ans[i][j] == -1) {
if (mn == -1 || x[i][j] < x[i][mn]) mn = j;
if (mx == -1 || x[i][j] > x[i][mx]) mx = j;
}
low.insert({x[i][mn], i});
high.insert({x[i][mx], i});
a[i] = {mn, mx};
}
while (low.size() > 0) {
int diff = 0;
int idx1 = -1, idx2 = -1;
// try min first
auto it1 = low.begin();
auto it2 = high.rbegin();
if (it1->second == it2->second) {
it2++;
}
diff = it2->first - it1->first;
idx1 = it1->second;
idx2 = it2->second;
// try max first
it1 = low.begin();
it2 = high.rbegin();
if (it1->second == it2->second) {
it1++;
}
if (it2->first - it1->first > diff) {
diff = it2->first - it1->first;
idx1 = it1->second;
idx2 = it2->second;
}
res += diff;
assert(diff >= 0);
ans[idx1][a[idx1].first] = r;
ans[idx2][a[idx2].second] = r;
low.erase({x[idx1][a[idx1].first], idx1});
low.erase({x[idx2][a[idx2].first], idx2});
high.erase({x[idx1][a[idx1].second], idx1});
high.erase({x[idx2][a[idx2].second], idx2});
}
}
allocate_tickets(ans);
return res;
}
