#include "tickets.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> ii;
typedef pair<ll,ii> iii;
typedef vector<ll> vi;
int vis[1510];
long long find_maximum(int k, std::vector<std::vector<int>> x) {
vector<vector<int> > ti;
int n=x.size();
int m=x[0].size();
ti.resize(n);
deque<iii> dq;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
ti[i].push_back(-1);
dq.push_back(iii(x[i][j],ii(i,j)));
}
}
sort(dq.begin(),dq.end());
memset(vis,0,sizeof vis);
vi aux;
for(int i=0;i<n/2;i++){
ll x=dq.back().first;
int a=dq.back().second.first;
int b=dq.back().second.second;
dq.pop_back();
aux.push_back(x);
ti[a][b]=0;
vis[a]=1;
}
int j=0;
while(j!=n/2){
ll x=dq.front().first;
int a=dq.front().second.first;
int b=dq.front().second.second;
if(!vis[a]){
j++;
aux.push_back(x);
vis[a]=1;
ti[a][b]=0;
}
dq.pop_front();
}
sort(aux.begin(),aux.end());
ll b=aux[(n/2)-1];
ll res=0;
for(int i=0;i<n;i++){
res+=abs(b-aux[i]);
}
allocate_tickets(ti);
return res;
}
