#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];
for(int i=0; i<n; i++){
for(int j=0; j<n; j++){
answer[i][j] = -1;
}
answer[i][maxind[i]]=0;
}
vector<pair<int,int> > sorted;
long long ans=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]];
continue;
}
if(x[i][minind[i]]>mi){
ans += x[i][maxind[i]]-mi;
continue;
}
ans += x[i][maxind[i]];
int vsmall = mi - x[i][minind[i]];
int vbig = x[i][maxind[i]] - mi;
int gain = vsmall - vbig;
sorted.push_back({gain, i});
}
sort(sorted.begin(), sorted.end());
reverse(sorted.begin(), sorted.end());
assert(sorted.size()%2==0);
for(int i=0; i<(int)sorted.size()/2; i++){
int 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, 0));
long long ans=0;
if(m==1){
ans=solvem1(n, k, x);
}
else if(k==1){
ans=solvek1(n, m, k, x, answer);
}
allocate_tickets(answer);
return ans;
}
