#include "tickets.h"
#include <vector>
#include <bits/stdc++.h>
// existen dos escenarios en el que la media sea maxima o en que sea minima
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef pair<int,int> ii;
const int MAX_N=1510;
bool vis[MAX_N];
vector<vi> ti;
vector<vi> p1,p0;
int c0,c1;
void cero(int i,int ro){
int t=p0[i].size()-1;
ti[i][p0[i][t]]=ro;
p0[i].pop_back();
c0++;
}
void uno(int i,int ro){
int t=p1[i].size()-1;
ti[i][p1[i][t]]=ro;
p1[i].pop_back();
c1++;
}
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n,m;
n=x.size(); m=x[0].size();
ti.resize(n);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++) ti[i].push_back(-1);
}
ll ans=0;
vector<ii> all;
for(int i=0;i<n;i++){
all.push_back(ii(1,i));
all.push_back(ii(0,i));
}
ii res;
for(int i=0;i<2*n;i++){
ll rp=0;
ll y;
int id=all[i].second;
if(all[i].first) y=x[id][0];
else y=x[id][m-1];
for(int j=0;j<n;j++){
if(id==j) continue;
rp+=max(abs(x[j][0]-y),abs(x[j][m-1]-y));
}
if(ans<rp){
res=all[i];
}
ans=max(ans,rp);
}
for(int j=0;j<n;j++){
if(res.second==j){
if(res.first) ti[j][0]=0;
else ti[j][m-1]=0;
}
ll y;
if(res.first) y=x[res.second][0];
else y=x[res.second][m-1];
if(abs(x[j][0]-y)>abs(x[j][m-1]-y)) ti[j][0]=0;
else ti[j][m-1]=0;
}
allocate_tickets(ti);
return ans;
}
