#include "tickets.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;
long long find_maximum(int k, vector<vector<int>> x) {
int n = x.size(), m = x[0].size();
vector<vector<int> > ans(n, vector<int>(m, -1));
vector<ii> mint(n, ii{INT_MAX, 0}),
maxt(n, ii{-1, 0});
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
mint[i] = min(mint[i], ii{x[i][j], j});
maxt[i] = max(maxt[i], ii{x[i][j], j});
}
int64_t sum = 0;
for (int i = 0; i < n; i++) {
sum += maxt[i].fi;
ans[i][maxt[i].se] = 0;
}
vector<ii> nho(n);
for (int i = 0; i < n; i++) nho[i] = ii{-mint[i].fi - maxt[i].fi, i};
sort(nho.begin(), nho.end());
reverse(nho.begin(), nho.end());
for (int i = 0; i < n/2; i++) {
sum += nho[i].fi;
int idx = nho[i].se;
swap(ans[idx][maxt[idx].se], ans[idx][mint[idx].se]);
}
allocate_tickets(ans);
return sum;
}
