#include "bits/stdc++.h"
#include "tickets.h"
#define pb push_back
using namespace std;
const long long inf = 1e15;
long long find_maximum(int k, vector<vector<int>> x) {
int n = x.size();
int m = x[0].size();
vector<vector<int>> ans(n, vector<int>(m, -1));
vector<vector<long long> > add(n, vector<long long>(k+1));
vector<int> ind(n);
for(int i = 0; i < n; i++){
vector<pair<int, int> > arr;
for(int j = 0; j < m; j++){
arr.pb({x[i][j], j});
}
sort(arr.begin(), arr.end());
long long now = 0;
for(int j = 0; j < k; j++){
now -= arr[j].first;
}
add[i][0] = now;
for(int j = 0; j < k; j++){
now += arr[(k - j - 1)].first;
now += arr[m - j - 1].first;
add[i][j+1] = now;
}
}
priority_queue<array<long long, 2> > pq;
long long mval = 0;
for(int i = 0; i < n; i++){
mval += add[i][0];
pq.push({add[i][ind[i]+1] - add[i][ind[i]], i});
}
for(int tur = 0; tur < n*k/2; tur++){
int i = pq.top()[1];
long long art = pq.top()[0];
pq.pop();
mval += art;
ind[i]++;
if(ind[i] != k){
pq.push({add[i][ind[i]+1] - add[i][ind[i]], i});
}
}
vector<vector<pair<int, int> > > par(n+1, vector<pair<int, int> >(n/2+2));
pair<int, int> lst = {0, 0};
for(int i = 0; i < n; i++){
par[i+1][lst.second + ind[i]] = lst;
lst = {i+1, lst.second + ind[i]};
}
int lstsm = 0, lstbg = k-1;
pair<int, int> now = {n, n*k/2};
while(now != make_pair(0, 0)){
pair<int, int> nxt = par[now.first][now.second];
int big = now.second - nxt.second;
int small = k - big;
vector<pair<int, int> > arr;
for(int j = 0; j < m; j++){
arr.pb({x[nxt.first][j], j});
}
sort(arr.begin(), arr.end());
for(int i = 0; i < small; i++){
ans[nxt.first][arr[i].second] = lstsm++;
if(lstsm == k) lstsm -= k;
}
for(int i = m-1; i >= m-big; i--){
ans[nxt.first][arr[i].second] = lstbg--;
if(lstbg == -1) lstbg += k;
}
now = nxt;
}
allocate_tickets(ans);
return mval;
}
