#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define sz(v) int(v.size())
typedef long long ll;
ll cost(int k, vector<vector<int>> x, vector<vector<int>> s) {
int n = sz(x), m = sz(x[0]);
vector<vector<int>> a(k);
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (s[i][j] != -1) {
a[s[i][j]].push_back(x[i][j]);
}
}
}
ll ans = 0;
for (auto& v : a) {
sort(v.begin(), v.end());
int m = v[sz(v)/2];
for (auto& c : v) ans += abs(c - m);
}
return ans;
}
ll find_maximum(int k, vector<vector<int>> x) {
int n = sz(x), m = sz(x[0]);
vector<pair<ll, int>> add;
for (int i = 0; i < n; i++) {
auto a = x[i];
sort(a.begin(), a.end());
for (int j = m-1; j >= m-k; j--) {
ll x = a[j] + a[j-(m-k)];
add.emplace_back(x, i);
}
}
sort(add.rbegin(), add.rend());
vector<int> cnt_plus(n);
for (int i = 0; i < k * (n / 2); i++) {
cnt_plus[add[i].second]++;
}
vector<vector<int>> neg(n), pos(n);
for (int i = 0; i < n; i++) {
vector<int> p(m); std::iota(p.begin(), p.end(), 0);
sort(p.begin(), p.end(), [&](int a, int b) { return x[i][a] < x[i][b]; });
int me = cnt_plus[i];
for (int j = 0; j < k-me; j++) {
neg[i].push_back(p[j]);
}
for (int j = 0; j < me; j++) {
pos[i].push_back(p[m-j-1]);
}
}
vector<vector<int>> ans(n, vector<int>(m, -1));
for (int r = 0; r < k; r++) {
vector<int> has(n, -1); // -1 = none, 1 = pos, 2 = neg
int need = n / 2;
for (int i = 0; i < n; i++) {
if (!sz(pos[i]) && need && has[i] == -1) {
has[i] = 2;
need--;
}
}
for (int i = 0; i < n; i++) {
if (sz(neg[i]) && need && has[i] == -1) {
has[i] = 2;
need--;
}
}
assert(need == 0);
need = n / 2;
for (int i = 0; i < n; i++) {
if (sz(pos[i]) && need && has[i] == -1) {
has[i] = 1;
}
}
for (int i = 0; i < n; i++) {
if (has[i] == 1) { // pos
ans[i][pos[i].back()] = r;
pos[i].pop_back();
} else if (has[i] == 2) { // neg
ans[i][neg[i].back()] = r;
neg[i].pop_back();
} else assert(false);
}
}
allocate_tickets(ans);
return cost(k, x, ans);
}
