#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pi;
typedef vector<int> vi;
typedef long long ll;
typedef pair<ll, ll> pl;
typedef vector<pl> vpl;
#define pb push_back
#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)
#define mp make_pair
#define f first
#define s second
long long find_maximum(int k, vector<vi> x) {
int n = sz(x);
int m = sz(x[0]);
vi lo(n, 0);
vi hi(n, m-1);
vector<vi> answer;
for(int i = 0; i < n; i++){
answer.pb(vi(m, -1));
}
ll ans = 0;
for(int round = 0; round < k; round++){
vpl sums;
for(int i = 0; i < n; i++){
sums.pb(mp(x[i][lo[i]]+x[i][hi[i]], i));
ans-=x[i][lo[i]];
}
sort(all(sums));
vi takehi(n, 0);
for(int i = n/2; i < n; i++){
ans+=sums[i].f;
takehi[sums[i].s] = 1;
}
for(int i = 0; i < n; i++){
if(takehi[i] == 0){
answer[i][lo[i]] = round;
lo[i]++;
}
else{
answer[i][hi[i]] = round;
hi[i]--;
}
}
}
allocate_tickets(answer);
return ans;
}
