#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 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-1){
cnt++;
vector<pair<int,int>> v;
for(int j = 0;j<n;j++){
if(i == j){
if(c == 0){
v.push_back({-1e9,j});
}
else v.push_back({1e9,j});
}
else{
if(x[j][m-1] < x[i][c]){
v.push_back({-1e9,j});
}
else if(x[j][0] > x[i][c]){
v.push_back({1e9,j});
}
else v.push_back({x[j][m-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-1] - x[i][c]);
if(x[v[j].second][m-1] < x[i][c])
now = -1e18;
}
if(now > maxi){
maxi = now;
opt1 = i;
opt2 = c;
}
}
}
assert(opt1 != -1 && opt2 != -1);
vector<pair<int,int>> v;
for(int j = 0;j<n;j++){
if(opt1 == j){
if(opt2 == 0){
v.push_back({-1e9,j});
}
else v.push_back({1e9,j});
}
else{
if(x[j][m-1] < x[opt1][opt2]){
v.push_back({-1e9,j});
}
else if(x[j][0] > x[opt1][opt2]){
v.push_back({1e9,j});
}
else v.push_back({x[j][m-1]-x[j][0],j});
}
}
// cout << opt1 << ' ' << opt2 << endl;
// cout << x[opt1][opt2] << endl;
sort(v.begin(),v.end());
for(int j = 0;j<n/2;j++){
answer[v[j].second][0] = 0;
}
for(int j = n/2;j<n;j++){
answer[v[j].second][m-1] = 0;
}
allocate_tickets(answer);
return maxi;
}
