#include "tickets.h"
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n = x.size();
int m = x[0].size();
std::vector<std::vector<int>> answer(n,vector<int>(m,-1));
ll ans=0;
vector<pair<ll,int>> pos;
for(int i=0;i<n;i++)
{
for(int j=0;j<k;j++)
{
ans-=x[i][j];
// answer[i][j]=j;
pos.push_back({x[i][j]+x[i][m-k+j],i});
}
}
sort(rbegin(pos),rend(pos));
vector<int> cnt(n+1);
for(int i=0;i<(n*k)/2;i++)
{
cnt[pos[i].second]++;
ans+=pos[i].first;
}
int l=0;
for(int i=0;i<n;i++)
{
for(int j=0;j<k-cnt[i];j++)
{
answer[i][j]=(l++)%k;
}
int r=l;
for(int j=m-1;j>=m-cnt[i];j--)
{
answer[i][j]=(r++)%k;
}
}
// for(int i=0;i<n;i++)
// {
// for(int j=0;j<m;j++)
// {
// cout<<answer[i][j]<<' ';
// }
// cout<<endl;
// }
allocate_tickets(answer);
return ans;
}
// int main()
// {
// int n,m,k;
// cin>>n>>m>>k;
// vector<vector<int>> x(n,vector<int>(m));
// for(int i=0;i<n;i++)
// {
// for(int j=0;j<m;j++)
// {
// cin>>x[i][j];
// }
// }
// cout<<find_maximum(k,x)<<endl;
// }
