#include "tickets.h"
#include <bits/stdc++.h>
#define dbg(x) cerr<<#x<<' '<<x<<endl;
#define ll long long
using namespace std;
void printvec(vector<ll>& vec)
{
for (auto &&e : vec)
{
cout << e << ' ';
}
cout << endl;
}
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n = x.size();
int m = x[0].size();
vector<pair<ll,ll>> fe(n,{0,m-1});
vector<vector<int>> ans(n,vector<int>(m,-1));
ll sm=0;
for (int r=0;r<k;r++)
{
vector<pair<ll,ll>> v;
vector<bool> bl(n);
for (int i=0;i<n;i++)
{
sm-=x[i][fe[i].first];
v.push_back({x[i][fe[i].second]+x[i][fe[i].first],i});
}
sort(v.begin(), v.end(),greater<pair<ll,ll>>());
for (int i=0;i<n/2;i++)
{
sm+=v[i].first;
bl[v[i].second]=1;
}
for (int i=0;i<n;i++)
{
if(bl[i]){ ans[i][fe[i].second]=r;fe[i].second--;}
else {ans[i][fe[i].first]=r;fe[i].first++;}
}
}
allocate_tickets(ans);
return sm;
}
