#include "tickets.h"
#include <vector>
#include<bits/stdc++.h>
#define pb emplace_back
using namespace std;
using ll = long long;
#ifdef KEV
#define DE(i, e) cerr << #i << ' ' << i << e
void debug(auto L, auto R) { while (L < R) cerr << *L << " \n"[L+1==R], ++L; }
#else
#define DE(...) 0
void debug(...) {}
#endif
vector<vector<int>> x, answer;
vector<deque<int>> so;
int k, n, m;
void init() {
so.resize(n, deque<int>(m));
int r = 0;
for (auto &i : so) {
iota(begin(i), end(i), 0);
sort(begin(i), end(i), [&](int a, int b) {
return x[r][a] < x[r][b];
});
++r;
}
answer.resize(n, vector<int>(m, -1));
}
ll calall() {
ll res = 0;
vector<vector<int>> val(k);
for (int i = 0;i < n;++i)
for (int j = 0;j < m;++j)
if (answer[i][j] != -1)
val[ answer[i][j] ].pb( x[i][j] );
for (auto &V : val) {
sort(begin(V), end(V));
int m = V[n/2];
for (int u : V)
res += abs(m - u);
}
return res;
}
void nobuild() {
for (int i = 0; i < n; i++) {
auto &row = answer[i];
for (int j = 0; j < m; j++)
if (j < k)
row[j] = j;
else
row[j] = -1;
}
}
int mxmx() { int res = 0; for (auto &V : x) res = max(res, *max_element(begin(V), end(V))); return res; }
void build01() {
vector<int> c0(n), id(n);
for (int i = 0;i < n;++i) {
c0[i] = count(begin(x[i]), end(x[i]), 0);
id[i] = i;
}
for (int d = 0;d < k;++d) {
sort(begin(id), end(id), [&](int a, int b) {
return c0[a] > c0[b];
});
for (int i = 0;i < n;++i) {
int row = id[i];
if (i < n/2) {
answer[row][ so[row][0] ] = d;
c0[ row ] -= x[row][so[row][0]] == 0;
so[row].pop_front();
}
else {
answer[row][ so[row].back() ] = d;
c0[ row ] -= x[row][so[row].back()] == 0;
so[row].pop_back();
}
}
}
}
long long find_maximum(int k, std::vector<std::vector<int>> x) {
n = x.size();
m = x[0].size();
::k = k;
::x = x;
init();
if (m == 1) nobuild();
else if (mxmx() <= 1) build01();
allocate_tickets(answer);
return calall();
}
