#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
typedef vector<int> vi;
typedef pair<int, int> pi;
typedef long long ll;
ll get_sum(vi elements, int b)
{
ll total = 0;
int n = elements.size();
for (int i = 0; i < n; i++)
{
total += abs(b - elements[i]);
}
return total;
}
ll find_min_sum(vi elements, int max)
{
const auto median_it = elements.begin() + elements.size() / 2;
std::nth_element(elements.begin(), median_it, elements.end());
auto median = *median_it;
return get_sum(elements, median);
// ll min_sum = 10E11;
// int opt_b = 0;
// for (int b = 0; b < max; b++)
// {
// ll sum = get_sum(elements, b);
// // cout << "b: " << sum << endl;
// if (sum < min_sum)
// {
// min_sum = sum;
// opt_b = b;
// }
// }
// return min_sum;
}
long long find_maximum(int k, std::vector<std::vector<int>> x)
{
int n = x.size();
vi elements;
vector<vi> answer;
int max = -1;
for (int i = 0; i < n; i++)
{
vi row = {0};
answer.push_back(row);
int current_el = x[i][0];
if (current_el > max)
max = current_el;
elements.push_back(current_el);
}
allocate_tickets(answer);
return find_min_sum(elements, max);
}
