#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
long long find_maximum(int k, vector<vector<int>> x) {
int n = x.size();
int m = x[0].size();
vector<vector<int>> answer;
for (int i = 0; i < n; i++) {
vector<int> row(m);
for (int j = 0; j < m; j++) {
row[j] = -1;
}
answer.push_back(row);
}
long long tot = 0;
for(int xx = 0;xx<k;xx++){
long long maxi = -1;
int opt1 = -1,opt2 = -1;
for(int i = 0;i<n;i++){
int cnt = 0;
for(int c = 0;c<m && cnt < 2;c+=m-xx-1){
cnt++;
vector<pair<int,int>> v;
for(int j = 0;j<n;j++){
if(i == j){
if(cnt == 1){
v.push_back({-2e9,j});
}
else v.push_back({2e9,j});
}
else{
if(x[j][m-xx-1] < x[i][c]){
v.push_back({-2e9,j});
}
else if(x[j][0] > x[i][c]){
v.push_back({2e9,j});
}
else v.push_back({x[j][m-xx-1]+x[j][0],j});
}
}
sort(v.begin(),v.end());
long long now = 0;
for(int j = 0;j<n/2;j++){
now += abs(x[v[j].second][0] - x[i][c]);
if(x[v[j].second][0] > x[i][c])
now = -1e18;
}
for(int j = n/2;j<n;j++){
now += abs(x[v[j].second][m-xx-1] - x[i][c]);
if(x[v[j].second][m-xx-1] < x[i][c])
now = -1e18;
}
if(now > maxi){
maxi = now;
opt1 = i;
opt2 = cnt;
}
}
}
assert(opt1 != -1 && opt2 != -1);
vector<pair<int,int>> v;
for(int j = 0;j<n;j++){
if(opt1 == j){
if(opt2 == 1){
v.push_back({-2e9,j});
}
else v.push_back({2e9,j});
}
else{
if(x[j][m-1] < x[opt1][(opt2-1) * (m-xx-1)]){
v.push_back({-2e9,j});
}
else if(x[j][0] > x[opt1][(opt2-1) * (m-xx-1)]){
v.push_back({2e9,j});
}
else v.push_back({x[j][m-1]+x[j][0],j});
}
}
sort(v.begin(),v.end());
for(int j = 0;j<n/2;j++){
answer[v[j].second][0] = xx;
x[v[j].second].erase(x[v[j].second].begin());
}
for(int j = n/2;j<n;j++){
answer[v[j].second][m-1] = xx;
x[v[j].second].erase(prev(x[v[j].second].end()));
}
tot += maxi;
}
allocate_tickets(answer);
return tot;
}
