#include "tickets.h"
#include<bits/stdc++.h>
using namespace std;
long long find_maximum(int k, vector<vector<int>> x)
{
int n = x.size();
int m = x[0].size();
int i,j;
vector<int> it[2];
vector<vector<int>> ans;
long long w=0;
for(i=0;i<n;i++)
{
it[0].push_back(0);
it[1].push_back(m-1);
}
for(i=0;i<n;i++)
{
ans.push_back({});
for(j=0;j<m;j++)
ans.back().push_back(-1);
}
while(k--)
{
priority_queue<pair<int,int>> pq;
for(i=0;i<n;i++)
{
pq.push({-x[i][it[1][i]]-x[i][it[0][i]],i});
w+=x[i][it[1][i]];
}
for(i=0;i<n/2;i++)
{
int xd=pq.top().second;
w+=pq.top().first;
pq.pop();
ans[xd][it[0][xd]++]=k;
}
while(!pq.empty())
{
int xd=pq.top().second;
pq.pop();
ans[xd][it[1][xd]--]=k;
}
}
allocate_tickets(ans);
return w;
}
