#include "tickets.h"
#include <vector>
#define KEV
#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<ll>> 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));
ll m = V[n/2];
for (ll 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();
}
}
}
}
struct PTR : pair<int,int> {
PTR(int x, int y) { first = x, second = y; }
int& operator()() { return x[first][second]; }
void set(int day) { answer[first][second] = day; }
};
int SM(int row) { return x[row][ so[row][0] ]; }
int BG(int row) { return x[row][ so[row].back() ]; }
ll getcal(vector<int> v) {
sort(begin(v), end(v));
ll res = 0, m = v[n/2];
for (int u : v) res += abs(m-u);
return res;
}
void pick(int day) {
vector<PTR> a;
for (int i = 0;i < n;++i) {
a.pb(i, so[i][0]);
a.pb(i, so[i].back());
}
sort(begin(a), end(a), [&](auto a, auto b) {
return a() < b();
});
DE(day, '\n');
for (int i = 0;i < n;++i)
assert(so[i].size() > 1);
vector<int> p1, p2;
vector<PTR> pl1, pl2;
auto tst = [&](vector<int> &p, vector<PTR> &pl) {
int cnt = 0;
vector<bool> vis(n), skip(n);
for (auto i : a) {
int row = i.first;
if (vis[row]) continue;
if (cnt >= n/2 && !skip[row]) {
skip[row] = true;
continue;
}
vis[row] = true;
pl.pb(i);
++cnt;
}
assert(cnt == n);
};
tst(p1, pl1);
reverse(begin(a), end(a));
tst(p2, pl2);
if (getcal(p2) > getcal(p1))
swap(pl1, pl2);
for (auto i : pl1) {
i.set(day);
int row = i.first;
if (SM(row) == i())
so[row].pop_front();
else
so[row].pop_back();
}
}
void solve() {
for (int d = 0;d < k;++d)
pick(d);
}
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();
else solve();
allocate_tickets(answer);
return calall();
}
