#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++){
int c=0;
vector<bool> b(n,0);
for(int i=0;i<n;i++){
if(a[i][r[i]]){
ans[i][r[i]--]=t;
b[i]=1;
x++;
if((++c)==n/2)break;
}
}
for(int i=0;i<n;i++)if(!b[i]){
if(c==n/2)break;
ans[i][r[i]--]=t;
b[i]=1;
c++;
}
for(int i=0;i<n;i++)if(!b[i]){
ans[i][l[i]]=t;
x-=a[i][l[i]++];
}
}
allocate_tickets(ans);
return x;
}
