#include "tickets.h"
#include "bits/stdc++.h"
using namespace std;
#define ar array
typedef long long ll;
//~ #define int ll
ll find_maximum(int k, vector<vector<int>> x) {
int n = x.size();
int m = x[0].size();
ll ans = -1, M;
vector<int> lor_(n);
auto check = [&](int mid){
ll res = 0;
ar<int, 2> all {};
vector<ar<int, 2>> diff;
vector<int> lor(n);
for(int i=0;i<n;i++){
for(int j=0;j<k;j++){
int l = j + m - k;
if(x[i][l] < mid){
res += (mid - x[i][j]);
lor[i]++; all[0]++;
continue;
}
if(mid < x[i][j]){
res += (x[i][l] - mid);
all[1]++;
continue;
}
lor[i]++;
all[0]++;
res += mid - x[i][j];
diff.push_back({-(mid - x[i][j]) + (x[i][l] - mid), i});
}
}
if(all[1] * 2 > n * k || (all[1] + (int)diff.size()) * 2 < n * k) return;
sort(diff.begin(), diff.end());
while(all[1] * 2 < n * k){
int i = diff.back()[1]; //, j = diff.back()[1] % m;
res += diff.back()[0];
diff.pop_back();
lor[i]--;
all[1]++;
}
if(all[1] * 2 != n * k) return;
if(res > ans){
ans = res;
M = mid;
lor_ = lor;
}
};
auto get = [&](vector<int>& lor){
vector<vector<int>> ans(n, vector<int>(m, -1));
vector<vector<int>> used(n, vector<int>(m));
vector<int> l(n), r(n);
for(int i=0;i<n;i++){
for(int j=0;j<lor[i];j++) used[i][j] = 1;
for(int j=m-(k - lor[i]);j<m;j++) used[i][j] = 1;
l[i] = 0, r[i] = m - 1;
}
for(int c=0;c<k;c++){
ar<int, 2> all {};
queue<int> q;
for(int i=0;i<n;i++){
while(!used[i][l[i]]) l[i]++;
while(!used[i][r[i]]) r[i]--;
if(x[i][r[i]] < M){
ans[i][l[i]] = c;
l[i]++; all[0]++;
} else if(M < x[i][l[i]]){
ans[i][r[i]] = c;
r[i]--; all[1]++;
} else {
ans[i][l[i]] = c;
l[i]++, all[0]++;
q.push(i);
}
}
assert(all[1] * 2 <= n);
while(!q.empty() && all[1] * 2 < n){
int i = q.front(); q.pop();
all[1]++;
ans[i][--l[i]] = -1;
ans[i][r[i]--] = c;
}
//~ assert(all[1] * 2 == n);
//~ while(all[1] * 2 != n);
}
return ans;
};
if(k == m){
vector<int> tot;
for(int i=0;i<n;i++) tot.insert(tot.end(), x[i].begin(), x[i].end());
sort(tot.begin(), tot.end());
check(tot[n * k / 2]);
allocate_tickets(get(lor_));
return ans;
}
for(int i=0;i<n;i++){
for(int j=0;j<m;j++){
check(x[i][j]);
}
}
//~ cout<<M<<endl;
//~ for(int i=0;i<n;i++) cout<<lor_[i]<<" ";
//~ cout<<endl;
allocate_tickets(get(lor_));
return ans;
//~ vector<int> l(n), r(n, m - 1);
//~ vector<int> lor_;
//~ auto check = [&](int mid){
//~ ll res = 0;
//~ ar<int, 2> all {};
//~ vector<ar<int, 2>> diff;
//~ vector<int> lor(n);
//~ for(int i=0;i<n;i++){
//~ if(x[i][r[i]] < mid || mid < x[i][l[i]]){
//~ if(mid < x[i][l[i]]) all[1]++, res += x[i][r[i]] - mid, lor[i] = 1;
//~ else all[0]++, res += mid - x[i][l[i]];
//~ continue;
//~ }
//~ all[0]++;
//~ res += mid - x[i][l[i]];
//~ diff.push_back({(x[i][r[i]] - mid) - (mid - x[i][l[i]]), i});
//~ }
//~ if(all[1] * 2 > n || (all[1] + (int)diff.size()) * 2 < n) return;
//~ sort(diff.begin(), diff.end());
//~ while(all[1] * 2 < n){
//~ all[0]--;
//~ all[1]++;
//~ res += diff.back()[0];
//~ lor[diff.back()[1]] = 1;
//~ diff.pop_back();
//~ }
//~ if(ans < res){
//~ ans = res;
//~ lor_ = lor;
//~ }
//~ };
//~ ll tot = 0;
//~ vector<vector<int>> res(n, vector<int>(m, -1));
//~ for(int c=0;c<k;c++){
//~ ans = -1;
//~ for(int i=0;i<n;i++){
//~ check(x[i][l[i]]);
//~ check(x[i][r[i]]);
//~ }
//~ tot += ans;
//~ for(int i=0;i<n;i++){
//~ if(lor_[i]) res[i][r[i]] = c, r[i]--;
//~ else res[i][l[i]] = c, l[i]++;
//~ }
//~ }
//~ allocate_tickets(res);
//~ return tot;
}
