#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define fi first
#define sc second
set< pair<int, pair<int,int>>> st;
vector<int> cur;
long long find_maximum(int k, vector<vector<int>> x) {
int n = x.size(), m = x[0].size();
for(int i = 0; i < k; i++)cur.push_back(0);
vector<vector<int>> ans(n);
for (int i = 0; i < n; i++) {
ans[i].resize(m);
for (int j = 0; j < m; j++){ ans[i][j] = -1; st.insert({x[i][j], {i,j}}); }
}
for(int z = 0; z < k*n/2; z++){
ans[ st.begin()->sc.fi ][ st.begin()->sc.sc ] = -2;
st.erase(st.begin());
}
long long resp = 0;
for (int i = 0; i < n; i++) {
int j = 0, kk =0;
while(kk < k && j < m){
if(ans[i][j] != -2)j++;
else{
if(cur[kk] < n/2){
resp -= x[i][j];
ans[i][j] = kk;
cur[kk]++;
j++;
}
kk++;
}
}
}
for (int i = 0; i < n; i++) {
int j = 0, kk = 0;
set<int> st;
for(int j = 0; j < m; j++)
if(ans[i][j] != -1)st.insert(ans[i][j]);
while(kk < k && j < m){
if(ans[i][j] != -1)j++;
else if(st.find(kk) != st.end())kk++;
else{
if(cur[kk] < n){
resp += x[i][j];
ans[i][j] = kk;
cur[kk]++;
j++;
}
kk++;
}
}
}
allocate_tickets(ans);
return resp;
}
