#include "tickets.h"
#ifdef NYAOWO
#include "grader.cpp"
#endif
#include <bits/stdc++.h>
#define For(i, a, b) for(int i = a; i <= b; i++)
#define Forr(i, a, b) for(int i = a; i >= b; i--)
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define sz(x) ((int)x.size())
#define eb emplace_back
#define int LL
using namespace std;
using i32 = int32_t;
using LL = long long;
using pii = pair<int, int>;
int cost_single(int n, vector<int> v) {
sort(all(v));
int s = 0;
int m = n / 2;
For(i, 0, m - 1) {
s += v[n - i - 1] - v[i];
}
return s;
}
int cost(int n, int m, int k, vector<vector<i32>> &x, vector<vector<i32>> &ans) {
vector<vector<int>> game(k);
For(i, 0, n - 1) For(j, 0, m - 1) if(ans[i][j] != -1) {
game[ans[i][j]].eb(x[i][j]);
}
int res = 0;
for(auto &g:game) res += cost_single(n, g);
return res;
}
int find_maximum(i32 _k, vector<vector<i32>> x) {
int k = _k;
int n = sz(x);
int m = sz(x[0]);
vector<vector<i32>> answer(n, vector<i32>(m, 0));
allocate_tickets(answer);
return cost(n, m, k, x, answer);
}
