#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
long long find_maximum(int k, vector<vector<int>> X) {
ll n = X.size(), m = X[0].size();
vector<vector<int>> allocations(n, vector<int>(m, -1));
vector<vector<ll>> x(n, vector<ll>(m));
for(ll i = 0; i < n; i++) for(ll j = 0; j < m; j++) x[i][j] = X[i][j];
vector<ll> ma(n), mi(n);
vector<pll> sum(n);
ll ans = 0;
for(ll i = 0; i < n; i++) {
ma[i] = *max_element(x[i].begin(), x[i].end()), mi[i] = *min_element(x[i].begin(), x[i].end());
ans -= mi[i];
sum[i] = {ma[i] + mi[i], i};
}
sort(sum.begin(), sum.end());
while(sum.size() > (n+1)/2) {
auto[s, i] = sum.back(); sum.pop_back();
allocations[i][max_element(x[i].begin(), x[i].end()) - x[i].begin()] = 0;
ans += s;
}
for(auto[s, i]: sum) allocations[i][min_element(x[i].begin(), x[i].end()) - x[i].begin()] = 0;
if(n % 2 == 1){
pll max_of_min = {0, 0};
for(auto[s, i]: sum) max_of_min = max(max_of_min, {mi[i], i});
ans += max_of_min.first;
}
allocate_tickets(allocations);
return ans;
}
