#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<int> a(n);
vector<vector<signed>> ret(n,vector<signed>(m,-1));
for (int i = 0; i < n; i++)
{
a[i]=i;
}
sort(all(a),[&x,&m](int _i, int _j){
if(x[_i][m-1]==x[_j][m-1]) return x[_i][0]>x[_j][0];
return x[_i][m-1]>x[_j][m-1];
});
vector<int> v;
for (int i = 0; i < n; i++)
{
if(i<n/2){
v.push_back(x[a[i]][m-1]);
ret[a[i]][m-1]=0;
}else{
v.push_back(x[a[i]][0]);
ret[a[i]][0]=0;
}
}
allocate_tickets(ret);
return calc(v);
}
