#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(i=0;i<n;i++){
pom=0;
for(int j=0;j<m;j++){
if(wyn[i][j]==0)wyn[i][j]=-1;
else if(i%2==0){
wyn[i][j]=pom;
pom++;
}
else{
wyn[i][j]=k-pom;
pom++;
}
}
}
allocate_tickets(wyn);
return ans;
}
