#include <bits/stdc++.h>
#include "tickets.h"
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<bool> vb;
typedef vector<vb> vvb;
#define ALL(x) begin(x), end(x)
#define pb push_back
#define mp make_pair
#define printBool(x) cout << ((x) ? "YES\n" : "NO\n")
#define printBoolR(x) {cout << ((x) ? "YES\n" : "NO\n"); return;}
inline ll nxt(){ll x;cin>>x;return x;}
#define fill_i(x) generate(ALL(x), nxt)
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n = x.size(), m = x[0].size();
vector<array<int,3>> numbs;
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
numbs.pb({x[i][j], i, j});
}
}
sort(ALL(numbs));
vvi s(n, vi(m, -1));
vvi rounds(k);
vi ctr(n, 0);
int p1 = 0, p2 = n*m-1;
vector<vector<array<int, 3>>> biggies(n);
vector<vector<array<int, 3>>> smalls(n);
if (k == 1) {
vector<pair<array<int,3>, array<int,3>>> L;
for (int i = 0; i < n; i++) {
ii MIN = {1e9, 1e9}, MAX = {-1,-1};
for (int j = 0; j < m; j++) {
MIN = min(MIN, {x[i][j], j});
MAX = max(MAX, {x[i][j], j});
}
L.push_back({{MIN.first, i, MIN.second}, {MAX.first, i, MAX.second}});
}
sort(ALL(L), [](const pair<array<int,3>, array<int,3>>& a, const pair<array<int,3>, array<int,3>>&b) {
return a.first[0] + a.second[0] > b.first[0] + b.second[0];
});
for (int i = 0; i < n/2; i++) biggies[L[i].second[1]].pb(L[i].second);
for (int i = n/2; i < n; i++) smalls[L[i].first[1]].pb(L[i].first);
} else
for (;;) {
while (p1 < n*m && ctr[numbs[p1][1]] == k) p1++;
if (p1 == n*m) break;
smalls[numbs[p1][1]].push_back(numbs[p1]);
ctr[numbs[p1][1]]++;
p1++;
while (ctr[numbs[p2][1]] == k) p2--;
biggies[numbs[p2][1]].push_back(numbs[p2]);
ctr[numbs[p2][1]]++;
p2--;
}
vvb didInRound(n, vb(k, false));
int i = 0, j = 0;
for (int r = 0; r < n*k/2; r++) {
while (j == smalls[i].size()) i++, j = 0;
didInRound[i][r%k] = true;
rounds[r%k].pb(smalls[i][j][0]);
s[i][smalls[i][j][2]] = r%k;
j++;
}
for (int i = 0; i < n; i++) {
int j = 0;
for (int r = 0; r < k; r++) if (!didInRound[i][r]) {
rounds[r].pb(biggies[i][j][0]);
s[i][biggies[i][j][2]] = r;
j++;
}
}
allocate_tickets(s);
ll score = 0;
for (int r = 0; r < k; r++) {
sort(ALL(rounds[r]));
int med = rounds[r][n/2];
for (int i = 0; i < n; i++) score += abs(med - rounds[r][i]);
}
return score;
}
