#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
const int nax = 1500;
int val[nax][2], n, m;
int best[nax];
long long mx_ans = 0;
void solve(int med) {
int cur[nax];
long long ret = 0;
int rit_cnt = 0;
vector<pair<int,int>>del;
for(int i=0; i<n; ++i) {
if(val[i][0] > med) {
cur[i] = 1;
ret += val[i][1] - med;
++rit_cnt;
} else if(val[i][1] < med) {
cur[i] = 0;
ret += med - val[i][0];
} else {
cur[i] = 0;
del.emplace_back((val[i][1]-med) - (med-val[i][0]), i);
ret += med - val[i][0];
}
}
if(rit_cnt * 2 > n) return;
sort(del.rbegin(), del.rend());
for(auto [d, i] : del) {
if(rit_cnt * 2 == n) break;
++rit_cnt;
ret += d;
cur[i] = 1;
}
if(rit_cnt * 2 != n) return;
if(ret > mx_ans) {
mx_ans = ret;
for(int i=0; i<n; ++i) {
best[i] = cur[i];
}
}
}
long long find_maximum(int k, vector<vector<int>> x) {
n = x.size();
m = x[0].size();
for(int i=0; i<n; ++i) {
val[i][0] = 2e9, val[i][1] = -1;
for(int j=0; j<m; ++j) {
val[i][0] = min(val[i][0], x[i][j]);
val[i][1] = max(val[i][1], x[i][j]);
}
}
for(int i=0; i<n; ++i) {
solve(val[i][0]);
solve(val[i][1]);
}
vector<vector<int>> ans(n, vector<int>(m, -1));
for(int i=0; i<n; ++i) {
for(int j=0; j<m; ++j) {
if(val[i][best[i]]==x[i][j]) {
ans[i][j] = 0;
break;
}
}
}
allocate_tickets(ans);
return mx_ans;
}
