#include<bits/stdc++.h>
#include "tickets.h"
using namespace std;
long long fnd_ans(int k,vector<vector<int>> v,vector<vector<int>> ans){
vector <int> vv[k];
int n=v.size();
int m=v[0].size();
for (int i=0; i<n; i++){
for (int j=0; j<m; j++){
if (ans[i][j]!=-1){
vv[ans[i][j]].push_back(v[i][j]);
}
}
}
long long sm=0,tt;
for (int i = 0; i < k; ++i) {
if (vv[i].empty()) continue;
auto &bucket = vv[i];
sort(bucket.begin(), bucket.end());
size_t mid = bucket.size() / 2;
long long median = (long long)bucket[mid];
for (int x : bucket) {
long long diff = (long long)x - median;
sm += (diff >= 0 ? diff : -diff);
}
}
return sm;
}
long long find_maximum(int k, vector<vector<int>> v){
int n=v.size();
int m=v[0].size();
vector<vector<int>> ans(n);
int sub_tsk3=1;
for (int i=0; i<n; i++){
for (int j=0; j<m; j++){
if (v[i][j]>1){
sub_tsk3=0;
}
}
}
if (m==1){
for (int i=0; i<n; i++){
ans[i].push_back(0);
}
}
else if(sub_tsk3==1){
if (n<5){return 0;}
vector <pair<int,int>> mn(n,{0,0});
for (int i=0; i<n; i++){
mn[i].second=i;
for (int j=0; j<m; j++){
mn[i].first+=v[i][j];
}
}
sort(mn.begin(),mn.end());
for (int i=0; i<n; i++){
for (int j=0; j<m; j++){
ans[i].push_back(-1);
}
}
for (int i=0; i<n; i++){
for (int j=0; j<k; j++){
if (i<n/2){ans[mn[i].second][j]=j;}
else{ans[mn[i].second][n-j-1]=j;}
}
}
}
else if (k==1){
vector <pair<int,int>> p;
vector <int> ps(n,0);
for (int i=0; i<n; i++){
p.push_back({v[i][0]+v[i][m-1],i});
}
sort(p.begin(),p.end());
for (int i=n/2; i<n; i++){
ps[p[i].second]=1;
}
for (int i=0; i<n; i++){
for (int j=0; j<m; j++){
if (j==0 && ps[i]==0){
ans[i].push_back(0);
}
else if (j==m-1 && ps[i]==1){
ans[i].push_back(0);
}
else{
ans[i].push_back(-1);
}
}
}
}
allocate_tickets(ans);
return fnd_ans(k,v,ans);
}
