#include "tickets.h"
#include <vector>
#include <bits/stdc++.h>
#define ll long long
#define f first
#define s second
using namespace std;
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n = x.size();
int m = x[0].size();
int curf[n], curl[n];
for(int i = 0; i < n; i++){
curf[i] = 0;
curl[i] = m - 1;
}
vector <vector <int> >al;
al.resize(n);
for(int i = 0; i < n; i++)al[i].resize(m);
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++)al[i][j] = -1;
}
ll ans = 0;
int cnt = -1;
while(k--){
cnt++;
multiset<pair<ll, int> > st;
for(int i = 0; i < n; i++){
int a= curf[i], b = curl[i];
st.insert({x[i][a], i});
st.insert({x[i][b], i});
}
int used[n];
while(!st.empty()){
pair<ll, int> cur = *st.begin();
st.erase(st.begin());
int ind = cur.s;
st.erase(st.find({x[ind][curl[ind]], ind}));
if(st.empty()) continue;
pair<ll, int> curr = *st.rbegin();
int ind1= curr.s;
st.erase(st.find(curr));
st.erase(st.find({x[ind1][curf[ind1]], ind1}));
ans += curr.f - cur.f;
used[ind] = 0;
used[ind1] = 1;
}
for(int i = 0; i < n; i++){
if(used[i]){
al[i][curl[i]] = cnt;
curl[i]--;
}
else al[i][curf[i]] = cnt, curf[i]++;
}
}
allocate_tickets(al);
return ans;
}
