#include "tickets.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;
ll find_maximum(int k, vector<vector<int>> _v){
int n = _v.size(), m = _v[0].size();
vector<deque<ll>> v(n);
for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) v[i].pb(_v[i][j]);
vector<vector<int>> pos(n, vector<int>(m, -1));
ll ans = 0;
vector<int> m1(n, 0), m2(n, m-1);
while(k--){
for(int i = 0; i < n; i++) ans+=v[i].back();
vector<int> s(n);
for(int i = 0; i < n; i++) s[i] = i;
sort(s.begin(), s.end(), [&](int a, int b){
return v[a][0]+v[a].back() < v[b][0]+v[b].back();
});
for(int i = 0; i < n; i++) pos[i][m2[i]] = k;
for(int i = 0; i < n/2; i++){
int x = s[i];
ans-=v[x][0]+v[x].back();
swap(pos[x][m1[x]], pos[x][m2[x]]);
m1[x]++;
v[x].pop_front();
}
for(int i = n/2; i < n; i++) v[s[i]].pop_back(), m2[s[i]]--;
}
allocate_tickets(pos);
return ans;
}
