#include <bits/stdc++.h>
using namespace std;
void allocate_tickets(vector<vector<int>> s);
using ind_min_max = pair<int, pair<int, int>>;
struct abs_d_comp
{
int abs_d;
ind_min_max over;
ind_min_max under;
};
bool compare_max(ind_min_max a, ind_min_max b)
{
return a.second.second>b.second.second;
}
bool compare_min(ind_min_max a, ind_min_max b)
{
return a.second.first<b.second.first;
}
bool compare_r(abs_d_comp a, abs_d_comp b)
{
return abs(a.abs_d)<abs(b.abs_d);
}
long long find_maximum(int k, vector<vector<int>> x)
{
int n = x.size();
int m = x[0].size();
vector<vector<int>> dupli{x};
vector<int> initial(m, -1);
vector<vector<int>> answer(n, initial);
vector<ind_min_max> min_max(0);
vector<int> occurrences(n, 0);
vector<int> dummy(n, 0);
vector<ind_min_max> max_des(0);
vector<ind_min_max> min_asc(0);
vector<ind_min_max> oversel(0);
vector<ind_min_max> undersel(0);
abs_d_comp inp;
abs_d_comp re;
vector<abs_d_comp> replacements(0);
vector<abs_d_comp> replacements_new(0);
vector<ind_min_max> max_sel(0);
vector<ind_min_max> min_sel(0);
for(int i=0; i<k; i++)
{
min_max.clear();
occurrences=dummy;
replacements.clear();
oversel.clear();
undersel.clear();
max_sel.clear();
min_sel.clear();
for(int j=0; j<n; j++)
{
min_max.push_back(make_pair(j, make_pair(x[j][0], x[j][m-i-1])));
}
max_des = min_max;
sort(max_des.begin(), max_des.end(), compare_max);
min_asc = min_max;
sort(min_asc.begin(), min_asc.end(), compare_min);
for(int j=0; j<(n/2); j++)
{
occurrences[max_des[j].first]++;
occurrences[min_asc[j].first]++;
}
for(int j=0; j<n; j++)
{
if(occurrences[j]==2)
{
oversel.push_back(min_max[j]);
}
else if(occurrences[j]==0)
{
undersel.push_back(min_max[j]);
}
else if(occurrences[j]==1)
{
if(find(min_asc.begin(), min_asc.begin()+(n/2), min_max[j])==min_asc.begin()+(n/2))
{
max_sel.push_back(min_max[j]);
}
else
{
min_sel.push_back(min_max[j]);
}
}
}
for(ind_min_max over: oversel)
{
for(ind_min_max under: undersel)
{
inp.over = over;
inp.under = under;
inp.abs_d = abs(over.second.second - under.second.second);
replacements.push_back(inp);
inp.abs_d = (-1)*abs(over.second.first - under.second.first);
replacements.push_back(inp);
}
}
sort(replacements.begin(), replacements.end(), compare_r);
while(not replacements.empty())
{
re = replacements[0];
replacements_new.clear();
if(re.abs_d>=0)
{
max_sel.push_back(re.under);
min_sel.push_back(re.over);
}
else
{
max_sel.push_back(re.over);
min_sel.push_back(re.under);
}
for(abs_d_comp bla: replacements)
{
if(not (bla.over==re.over || bla.under==re.under))
{
replacements_new.push_back(bla);
}
}
replacements=replacements_new;
}
for(ind_min_max bla: max_sel)
{
for(int j=m-1; j>=0; j--)
{
if(answer[bla.first][j]==(-1))
{
answer[bla.first][j]=i;
break;
}
}
x[bla.first].erase(x[bla.first].end()-1);
}
for(ind_min_max bla: min_sel)
{
for(int j=0; j<m; j++)
{
if(answer[bla.first][j]==-1)
{
answer[bla.first][j]=i;
break;
}
}
x[bla.first].erase(x[bla.first].begin());
}
}
allocate_tickets(answer);
long long max_sum = 0;
set<int> summate;
for(int i=0; i<k; i++)
{
summate.erase(summate.begin(), summate.end());
for(int a=0; a<n; a++)
{
for(int b=0; b<m; b++)
{
if(answer[a][b]==i)
{
summate.insert(dupli[a][b]);
}
}
}
int counter{};
auto median_it(summate.begin());
for(auto it=summate.begin(); it!= summate.end(); it++)
{
counter++;
if(counter==(n/2))
{
median_it=it;
break;
}
}
for(auto it=summate.begin(); it!=summate.end(); it++)
{
max_sum += abs((*it)-(*median_it));
}
}
return max_sum;
}
