#include <bits/stdc++.h>
#include "tickets.h"
using namespace std;
const int MAX_N = 1505;
int N, M, K, median;
long long ans;
int cnt[MAX_N], id[MAX_N];
int sz[MAX_N];
long long find_maximum(int k, vector <vector <int>> x) {
N = x.size(), M = x[0].size(), K = k;
vector <vector <int>> answer(N, vector <int> (M, -1));
if(M == 1) {
vector <int> vec;
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
answer[i][j] = 0;
vec.push_back(x[i][j]);
}
}
sort(vec.begin(), vec.end());
median = vec[N / 2];
for(int i = 0; i < N; i++) {
ans += abs(median - vec[i]);
}
}
else if(K == 1) {
vector <int> vec;
for(int i = 0; i < N; i++) {
answer[i][M - 1] = 0;
vec.push_back(x[i][M - 1]);
}
sort(vec.begin(), vec.end());
median = vec[N / 2];
for(int i = 0; i < N; i++) {
ans += abs(median - vec[i]);
}
}
else {
for(int i = 0; i < N; i++) {
for(int j = 0; j < M; j++) {
cnt[i] += x[i][j];
}
}
iota(id, id + N, 0);
sort(id, id + N, [&](const int &a, const int &b) {
return cnt[a] < cnt[b];
});
for(int k = 0; k < K; k++) {
vector <int> vec;
for(int i = 0; i < N; i++) {
if(id[i] < N / 2) {
vec.push_back(x[i][sz[i]]);
answer[i][sz[i]++] = k;
}
else {
vec.push_back(x[i][M - sz[i] - 1]);
answer[i][M - (sz[i]++) - 1] = k;
}
}
sort(vec.begin(), vec.end());
median = vec[N / 2];
for(int i = 0; i < N; i++) {
ans += abs(median - vec[i]);
}
}
}
allocate_tickets(answer);
return ans;
}
