#include <bits/stdc++.h>
#include "tickets.h"
using namespace std;
using ll=long long;
ll find_maximum(int k, vector<vector<int>>x){
int n,m; n=x.size(); m=x[0].size();
vector<int>bplus(n), bminus(n);
for(int i=0;i<n;i++)bplus[i]=m;
for(int i=0;i<n;i++)bminus[i]=k;
vector<vector<int>>wyn(n);
for(int i=0;i<n;i++)wyn[i].resize(m);
for(int i=0;i<n;i++)for(int j=0;j<m;j++)wyn[i][j]=0;
priority_queue<pair<int,int>>pq;
ll ans=0;
for(int i=0;i<n;i++)for(int j=0;j<k;j++){
ans-=x[i][j];
wyn[i][j]=-1;
}
for(int i=0;i<n;i++)pq.push({x[i][m-1]+x[i][k-1],i});
ll pom=0; pair<int,int>cur; int i;
while(2*pom<n*k){
cur=pq.top(); ans+=cur.first;
pq.pop();
i=cur.second;
bplus[i]--; bminus[i]--;
wyn[i][bminus[i]]=0;
wyn[i][bplus[i]]=1;
pom++;
if(bminus[i]>0)pq.push({x[i][bminus[i]-1]+x[i][bplus[i]-1],i});
}
for(int i=0;i<n;i++){for(int j=0;j<m;j++){if(wyn[i][j]==0)wyn[i][j]=-1;else if(wyn[i][j]==-1) wyn[i][j]=-2;else wyn[i][j]=1;}}
int d=0,it=0; pom=-1; bool tab[n]; for(int i=0;i<n;i++)tab[i]=1; int all=0;
vector<int>bpc;
bpc=bplus;
while(all<n){
pom++; pom%=n;
if(!tab[i])continue;
if(bplus[pom]==m){
all++;
tab[pom]=0;
continue;
}
wyn[pom][bplus[pom]]=d;
bplus[pom]++;
it++;
if(2*it==n){
it=0;
d++;
}
}
int j;
for(int i=0;i<n;i++){
j=0; it=bpc[i]; d=0;
while(wyn[i][j]==-2){
if(it==m)wyn[i][j]=d;
else{
if(wyn[i][it]==d){
it++; d++; continue;
}
else wyn[i][j]=d;
}
d++;
j++;
}
}
allocate_tickets(wyn);
return ans;
}
