#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const ll INF = 1e17;
void dbg(vector<ll> xx) {
cout << "DBG: ";
for (auto x: xx) cout << x << " ";
cout << "\n";
}
ll calc_cost(vector<ll> x) {
int n = x.size();
sort(x.begin(), x.end());
ll cost = 0;
for (int i = 0; i < n; i++) cost += abs(x[n/2] - x[i]);
return cost;
/*
ll currCost = 0;
for (int i = 1; i < n; i++) currCost += x[i] - x[0];
ll mn = currCost;
for (int i = 1; i < n; i++) {
ll dis = (x[i] - x[i-1]);
currCost += dis * i;
currCost -= dis * (n - i);
mn = min(mn, currCost);
}
return mn;*/
}
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n = x.size();
int m = x[0].size();
vector<vector<int>> cons(n, vector<int>(m, 0));
vector<ll> arr;
for (int i = 0; i < n; i++) arr.push_back(x[i][0]);
/*
ll maxCost = calc_cost(arr);
int bestPref = -1;
for (int i = 0; i < n; i++) {
}*/
allocate_tickets(cons);
return calc_cost(arr);
}
