#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();
ll sm=0;
vector<pair<ll,ll>> v;
vector<bool> bl(n);
for (int i=0;i<n;i++)
{
sm-=x[i][0];
v.push_back({x[i].back()+x[i][0],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;
}
vector<vector<int>> ans(n,vector<int>(m,-1));
for (int i=0;i<n;i++)
{
if(bl[i]) ans[i].back()=0;
else ans[i][0]=0;
}
allocate_tickets(ans);
return sm;
}
