#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define sz(a) (int)a.size()
#define all(a) a.begin(), a.end()
#define rall(a) a.rbegin(), a.rend()
int n;
int calc(vector<int> v){
sort(all(v));
int med=v[(sz(v)-1)/2];
int ans=0;
for (int i = 0; i < sz(v); i++) ans+=abs(v[i]-med);
return ans;
}
long long find_maximum(signed k, std::vector<std::vector<signed>> x) {
n=sz(x);
int m=sz(x[0]);
vector<pair<int,int>> a(n);
vector<vector<signed>> ret(n,vector<signed>(m,-1));
for (int i = 0; i < n; i++)
{
a[i]={x[i][m-1], i};
}
sort(rall(a));
vector<int> v;
for (int i = 0; i < n; i++)
{
if(i<n/2){
v.push_back(x[a[i].second][m-1]);
ret[a[i].second][m-1]=0;
}else{
v.push_back(x[a[i].second][0]);
ret[a[i].second][0]=0;
}
}
allocate_tickets(ret);
return calc(v);
}
