#include "tickets.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll,ll> ii;
typedef pair<ii,ll> 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;
vector<iii> r1,r2;
int n=x.size();
int m=x[0].size();
t1.resize(n);
t2.resize(n);
for(int i=0;i<n;i++)
for(int j=0;j<m;j++) {
t1[i].push_back(-1);
t2[i].push_back(-1);
}
for(int i=0;i<n;i++){
r2.push_back(iii(ii(x[i][m-1],x[i][0]),i));
r1.push_back(iii(ii(x[i][0],x[i][m-1]),i));
}
sort(r1.begin(),r1.end());
vector<ll> aux;
for(int i=0;i<n;i++){
int id=r1[i].second;
if(i<n/2){
aux.push_back(r1[i].first.first);
t1[id][0]=0;
}
else{
t1[id][m-1]=0;
aux.push_back(r1[i].first.second);
}
}
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]));
}
aux.clear();
sort(r2.begin(),r2.end());
for(int i=0;i<n;i++){
int id=r2[i].second;
if(i<n/2){
aux.push_back(r2[i].first.second);;
t2[id][0]=0;
}
else{
t2[id][m-1]=0;
aux.push_back(r2[i].first.first);
}
}
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;
}
}
