#include "tickets.h"
#include<bits/stdc++.h>
using namespace std;
long long solvem1(int n, int k, vector<vector<int> >& x){
vector<int> s(n);
for(int i=0; i<n; i++){
s[i]=x[i][0];
}
sort(s.begin(), s.end());
int mi=s[n/2];
long long ans=0;
for(int i=0; i<n; i++){
if(s[i]<mi){
ans += mi-s[i];
}
else{
ans += s[i]-mi;
}
}
return ans;
}
long long solvek1(int n, int m, int k, vector<vector<int> >& x, vector<vector<int> >& answer){
vector<int> minind(n, 0);
vector<int> maxind(n, 0);
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
if(x[i][j] < x[i][minind[i]]){
minind[i]=j;
}
if(x[i][j] > x[i][maxind[i]]){
maxind[i]=j;
}
}
}
vector<int> nums;
for(int i=0; i<n; i++){
nums.push_back(x[i][maxind[i]]);
nums.push_back(x[i][minind[i]]);
}
sort(nums.begin(), nums.end());
int mi=nums[n-1];
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
answer[i][j] = -1;
}
answer[i][maxind[i]]=0;
}
vector<pair<long long,int> > sorted;
long long ans=0;
int cntsmall=0;
for(int i=0; i<n; i++){
if(x[i][maxind[i]]<mi){
answer[i][maxind[i]]=-1;
answer[i][minind[i]]=0;
ans += mi - x[i][minind[i]];
cntsmall++;
continue;
}
if(x[i][minind[i]]>mi){
ans += x[i][maxind[i]]-mi;
continue;
}
assert(x[i][minind[i]]<=mi && mi<=x[i][maxind[i]]);
int vsmall = mi - x[i][minind[i]];
int vbig = x[i][maxind[i]] - mi;
ans += vbig;
long long gain = vsmall - vbig;
sorted.push_back({gain, i});
}
sort(sorted.begin(), sorted.end());
reverse(sorted.begin(), sorted.end());
for(int i=0; cntsmall<n/2; i++, cntsmall++){
long long gain=sorted[i].first;
int ind=sorted[i].second;
ans += gain;
answer[ind][maxind[ind]]=-1;
answer[ind][minind[ind]]=0;
}
return ans;
}
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n = x.size();
int m = x[0].size();
vector<vector<int> > answer(n, vector<int> (m, -1));
long long ans=0;
if(m==1){
for(int i=0; i<n; i++){
for(int j=0; j<m; j++){
answer[i][j]=0;
}
}
ans=solvem1(n, k, x);
}
else if(k==1){
ans=solvek1(n, m, k, x, answer);
}
allocate_tickets(answer);
return ans;
}
