#include "tickets.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#define pii pair<int,int>
#define fs first
#define sc second
long long find_maximum(int k, std::vector<std::vector<int>> a) {
int n = a.size();
int m = a[0].size();
long long x=0;
vector<vector<int>> ans(n,vector<int>(m,-1));
vector<int> l(n,0),r(n,m-1);
for(int t=0;t<k;t++){
vector<pii> v;
for(int i=0;i<n;i++){
x-=a[i][l[i]];
v.push_back({a[i][l[i]]+a[i][r[i]],i});
}
sort(v.begin(),v.end());
for(int i=0;i<n/2;i++)ans[v[i].sc][l[v[i].sc]++]=t;
for(int i=n/2;i<n;i++){
x+=v[i].fs;
ans[v[i].sc][r[v[i].sc]--]=t;
}
}
allocate_tickets(ans);
return x;
}
