#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define mp make_pair
#define pb push_back
#define fi first
#define se second
long long find_maximum(int k, vector<vector<int> > x){
int n=x.size(), m=x[0].size();
for (int i=0; i<n; ++i)sort(x[i].begin(), x[i].end());
vector<pii> ord;
vector<vector<int> > ans(n, vector<int>(m));
for (int i=0; i<m; ++i){
vector<int> temp;
for (int j=0; j<n; ++j)temp.pb(x[j][i]);
sort(temp.begin(), temp.end());
int sum=0;
for (auto a:temp)sum+=abs(a-temp[n/2]);
ord.pb(mp(sum, i));
}
sort(ord.begin(), ord.end(), greater<pii>());
int res=0;
for (int i=0; i<m; ++i){
if (i<k)res+=ord[i].fi;
for (int j=0; j<n; ++j)ans[j][i]=x[j][ord[i].se];
}
allocate_tickets(ans);
return res;
}
