#include <bits/stdc++.h>
#include "tickets.h"
using namespace std;
#define pb push_back
#define se second
#define fi first
long long sum(vector<int> tab){
int n=tab.size();
long long res=0;
sort(tab.begin(),tab.end());
for (long long i = 0; i < n; ++i)
{
res+=abs(tab[i]-tab[n/2]);
}
return res;
}
long long find_maximum(int k, std::vector<std::vector<int>> x) {
long long n = x.size();
int m = x[0].size();
vector<std::vector<int>> ans(n,vector<int> (m,-1));
long long res=0;
vector<pair<int,int>> mx;
vector<pair<int,int>> mn;
for (int i = 0; i < n; ++i)
{
mx.pb({x[i][m-1],i});
mn.pb({x[i][0],i});
}
vector<int> tab;
sort(mx.begin(),mx.end());
sort(mn.begin(),mn.end());
for (int i = n/2; i < n; ++i)
{
ans[mx[i].se][m-1]=0;
tab.pb(mx[i].fi);
}
for (int i = 0; i < n; ++i)
{
if(ans[mn[i].se][m-1]==0) continue;
ans[mn[i].se][0]=0;
tab.pb(mn[i].fi);
}
allocate_tickets(ans);
res+=sum(tab);
return res;
}
