#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
vector<vector<int>>answer;
vector<deque<int>>mat;
vector<int>st;
vector<int>dr;
long long alege(int id){
int n=mat.size();
vector<bool>ans(n,0);
int i,j;
long long rasp=0;
for(i=0;i<n;++i){
int cntm=0,cntM=0;
long long summ=0,sumM=0;
long long summij=0;
vector<pair<int,int>>mij;
vector<bool>util(n,1);
util[i]=0;
for(j=0;j<n;++j)
if(i!=j){
if(mat[j].back()<mat[i][0]){
++cntm;
summ+=mat[i][0]-mat[j][0];
util[j]=0;
}
else
if(mat[i][0]<mat[j][0]){
++cntM;
sumM+=mat[j].back()-mat[i][0];
}
else{
summij+=mat[j].back()-mat[i][0];
mij.push_back({mat[j][0]+mat[j].back(),j});
}
}
if(cntm<n/2 && cntM<=n/2){
sort(mij.begin(),mij.end());
summij+=summ+sumM;
int alegem=n/2-1-cntm;
for(j=0;j<alegem;++j){
summij+=2*mat[i][0]-mij[j].first;
util[mij[j].second]=0;
}
if(rasp<summij){
rasp=summij;
ans=util;
}
}
}
for(i=0;i<n;++i)
if(ans[i]){
answer[i][dr[i]]=id;
dr[i]--;
mat[i].pop_back();
}
else{
answer[i][st[i]]=id;
st[i]++;
mat[i].pop_front();
}
return rasp;
}
long long find_maximum(int k,vector<vector<int>>x){
int n = x.size();
int m = x[0].size();
st.resize(n,0);
dr.resize(n,m-1);
int i,j;
long long sum=0;
for(i=0;i<n;++i){
vector<int>row;
deque<int>deq;
for(j=0;j<m;++j){
row.push_back(-1);
deq.push_back(x[i][j]);
}
answer.push_back(row);
mat.push_back(deq);
}
for(i=0;i<k;++i)
sum+=alege(i);
allocate_tickets(answer);
return sum;
}
