#include "tickets.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n = x.size();
int m = x[0].size();
std::vector<std::vector<int>> answer(n,vector<int>(m,-1));
vector<int> mia(n,0);
vector<int> mxa(n,m-1);
ll sm=0;
for(int rd=0;rd<k;rd++)
{
vector<pair<int,int>> ord;
for(int i=0;i<n;i++)
{
sm-=x[i][mia[i]];
answer[i][mia[i]]=rd;
ord.push_back({x[i][mia[i]]+x[i][mxa[i]],i});
mia[i]++;
}
sort(rbegin(ord),rend(ord));
for(int i=0;i<n/2;i++)
{
sm+=ord[i].first;
int j=ord[i].second;
mia[j]--;
answer[j][mia[j]]=-1;
answer[j][mxa[j]]=rd;
mxa[j]--;
}
}
allocate_tickets(answer);
return sm;
}
