#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> > t1,t2;
int n=x.size();
int m=x[0].size();
t1.resize(n);
t2.resize(n);
deque<iii> o1,o2;
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
t1[i].push_back(-1);
t2[i].push_back(-1);
o2.push_back(iii(x[i][j],ii(i,j)));
o1.push_back(iii(x[i][j],ii(i,j)));
}
}
sort(o2.begin(),o2.end());
sort(o1.begin(),o1.end());
memset(vis,0,sizeof vis);
vi aux;
int j=0;
while(j!=n/2){
ll x=o1.back().first;
int a=o1.back().second.first;
int b=o1.back().second.second;
o1.pop_back();
if(!vis[a]){
aux.push_back(x);
t1[a][b]=0;
vis[a]=1;
j++;
}
}
j=0;
while(j!=n/2){
ll x=o1.front().first;
int a=o1.front().second.first;
int b=o1.front().second.second;
if(!vis[a]){
j++;
aux.push_back(x);
vis[a]=1;
t1[a][b]=0;
}
o1.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]);
}
memset(vis,0,sizeof vis);
aux.clear();
j=0;
while(j!=n/2){
ll x=o2.front().first;
int a=o2.front().second.first;
int b=o2.front().second.second;
if(!vis[a]){
j++;
aux.push_back(x);
vis[a]=1;
t2[a][b]=0;
}
o2.pop_front();
}
j=0;
while(j!=n/2){
ll x=o2.back().first;
int a=o2.back().second.first;
int b=o2.back().second.second;
o2.pop_back();
if(!vis[a]){
aux.push_back(x);
t2[a][b]=0;
vis[a]=1;
j++;
}
}
sort(aux.begin(),aux.end());
b=aux[(n/2)-1];
ll res1=0;
for(int i=0;i<n;i++){
res1+=abs(b-aux[i]);
}
if(res>res1){
allocate_tickets(t1);
return res;
}
else{
allocate_tickets(t2);
return res1;
}
}
