#include <bits/stdc++.h>
#include "tickets.h"
//#include "grader.cpp"
using namespace std;
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << " " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << " " << j << " " << #i << " " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef pair<int,pii>pi2;
//allocate_tickets(vector<vector<int>>)
long long find_maximum(int k, vector<vector<int>>arr){
int n = arr.size();
int m = arr[0].size();
set<pair<long long,pii>>se;
for(int x=0;x<n;x++){
for(int y=0;y<m;y++){
se.insert({arr[x][y],{x,y}});
}
}
//k==1
vector<vector<int>>ans;
ans.resize(n);
for(int x=0;x<n;x++){
ans[x]=vector<int>(m,-1);
}
vector<long long>v;
bool done[n+5];
memset(done,0,sizeof(done));
for(int x=0;x<n/2;x++){
auto it=se.begin();
auto it2=prev(se.end());
pi2 hold=*it;
pi2 hold2=*it2;
if(hold.second.first==hold2.second.first){
//same color
while(it->second.first==hold.second.first) it++;
while(it2->second.first==hold.second.first) it2--;
if(abs(it->first-hold.first)<=abs(it2->first-hold2.first)){
hold=*it;
}
else{
hold2=*it2;
}
}
for(int y=0;y<m;y++){
se.erase({arr[hold.second.first][y],{hold.second.first,y}});
se.erase({arr[hold2.second.first][y],{hold2.second.first,y}});
}
ans[hold.second.first][hold.second.second]=0;
ans[hold2.second.first][hold2.second.second]=0;
v.push_back(hold.first);
v.push_back(hold2.first);
}
long long counter=0;
for(int y=0;y<n;y++){
counter+=abs(v[y]-v[n/2]);
}
allocate_tickets(ans);
return counter;
}
