#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
#define all(a) (a).begin(), (a).end()
template<typename T>
int len(T &a){
return a.size();
}
mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n = x.size();
int m = x[0].size();
vector<vector<int>> ans(n, vector<int>(m, -1));
vector<int> v;
vector<int> cnt(n);
for(int i = 0; i < n; i ++){
for(int j = 0; j < m; j ++){
cnt[i] += x[i][j];
}
}
vector<int> l(n, 0), r(n, m - 1);
ll mx = 0;
vector<int> ind(n);
iota(all(ind), 0);
for(int lev = 0; lev < k; lev ++){
sort(all(ind), [&](int i, int j){return cnt[i] < cnt[j];});
vector<int> v(n);
for(int _ = 0; _ < n / 2; _ ++){
int i = ind[_];
v[i] = x[i][l[i]];
ans[i][l[i]] = lev;
cnt[i] -= v[i];
//cout << i << ' ';
l[i] ++;
}
for(int _ = n / 2; _ < n; _ ++){
int i = ind[_];
v[i] = x[i][r[i]];
ans[i][r[i]] = lev;
cnt[i] -= v[i];
r[i] --;
}
sort(all(v));
for(int i = 0; i < n; i ++){
mx += abs(v[i / 2] - v[i]);
}
}
allocate_tickets(ans);
return mx;
}
