#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<ll,ll> ii;
typedef pair<ll,ii> iii;
const int MAX_N=1510;
bool vis[MAX_N];
vector<vi> ti;
vector<vi> mat;
vector<ii> vma;
int n,m;
long long find_maximum(int k, std::vector<std::vector<int>> x) {
n=x.size(); m=x[0].size();
mat=x;
ti.resize(n);
for(int i=0;i<n;i++){
for(int j=0;j<m;j++) ti[i].push_back(-1);
}
vector<int> idi,ida;
for(int i=0;i<n;i++){
idi.push_back(0);
ida.push_back(m-1);
}
ll ans=0;
for(int ro=0;ro<k;ro++){
vector<ii> su;
for(int i=0;i<n;i++){
su.push_back(ii(-(x[i][idi[i]]+x[i][ida[i]]),i));
}
sort(su.begin(),su.end());
for(int i=0;i<n;i++){
if(i<n/2){
int id=su[i].second;
ti[id][ida[id]]=ro;
ans+=x[id][ida[id]];
ida[id]--;
}
else {
int id=su[i].second;
ti[id][idi[id]]=ro;
ans-=x[id][idi[id]];
idi[id]++;
}
}
}
allocate_tickets(ti);
return ans;
}
