#include <iostream>
#include <algorithm>
#include "tickets.h"
#include <vector>
#define ll long long
using namespace std;
const ll inf = 1e18 + 69;
#define pii pair<int, int>
vector<vector<int>> answer;
ll ans;
long long find_maximum(int k, vector<vector<int>> x) {
int n = x.size();
int m = x[0].size();
answer.resize(n);
for (int i = 0; i < n; i++) {
answer[i].resize(m, -1);
}
if (m == 1) {
for (int i = 0; i < n; i++) {
answer[i][0] = 0;
}
vector<int> v;
for (int i = 0; i < n; i++) {
v.push_back(x[i][0]);
}
sort(v.begin(), v.end());
ll b = v[n / 2];
for (int i = 0; i < n; i++) {
ans += abs(b - v[i]);
}
}
else if (k == 1) {
vector<pii> d(n);
for (int i = 0; i < n; i++) {
d[i] = pii(x[i][m - 1] - x[i][0], i);
ans += d[i].first;
}
sort(d.begin(), d.end());
for (int i = 0; i < n / 2; i++) {
answer[d[i].second][m - 1] = 0;
}
for (int i = n / 2; i < n; i++) {
answer[d[i].second][0] = 0;
}
}
allocate_tickets(answer);
return ans;
}
