#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> ans;
// 1 5
// 10 10
// 8 12
// 12 20
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++) {
vector<int> low(n), high(n);
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[i] = x[i][mn];
high[i] = x[i][mx];
a[i] = {mn, mx};
}
vector<int> best(n);
long long bestDiff = -1;
for (int md = 0; md < n; md++) {
int median = low[md];
vector<int> pick(n);
int cntLow = 0, cntHigh = 0;
vector<pair<int, int>> v;
for (int i = 0; i < n; i++)
if (high[i] <= median) { pick[i] = a[i].first; cntLow++; }
else if (low[i] > median) { pick[i] = a[i].second; cntHigh++; }
else {
pick[i] = a[i].first;
v.push_back({low[i] + high[i] - 2 * median, i});
}
if (cntHigh > n / 2) continue;
if (cntLow > n / 2) continue;
sort(v.rbegin(), v.rend());
for (int i = 0; i < n / 2 - cntHigh; i++) {
int j = v[i].second;
pick[j] = a[j].second;
}
long long diff = 0;
vector<int> b(n);
for (int i = 0; i < n; i++) b[i] = x[i][pick[i]];
for (int i = 0; i < n; i++) assert(pick[i] == a[i].first || pick[i] == a[i].second);
sort(b.begin(), b.end());
for (int i = 0; i < n / 2; i++) diff += b[n - i - 1] - b[i];
if (diff > bestDiff) {
bestDiff = diff;
best = pick;
}
}
for (int i = 0; i < n; i++) ans[i][best[i]] = r;
res += bestDiff;
}
allocate_tickets(ans);
return res;
}
