#include <bits/stdc++.h>
#include "tickets.h"
//~ #include "grader.cpp"
using namespace std;
#define ll long long
ll find_maximum(int k, vector <vector <int> > x) {
int n = x.size();
int m = x[0].size();
ll res = 0;
for(int i = 0 ; i < n ; i++){
for(int j = m - k ; j < m ; j++){
res += x[i][j];
}
}
vector <vector <int> > g(n, vector <int>(k));
for(int i = 0 ; i < n ; i++){
for(int j = 0 ; j < k ; j++){
g[i][j] = x[i][j] + x[i][m - k + j];
}
}
set <pair <int, int> > s;
for(int i = 0 ; i < n ; i++){
s.insert(make_pair(g[i][0], i));
}
vector <int> cnt(n);
for(int i = 0 ; i < n * k / 2 ; i++){
int row = s.begin()->second;
s.erase(s.begin());
res -= g[row][cnt[row]];
cnt[row]++;
if(cnt[row] < k){
s.insert(make_pair(g[row][cnt[row]], row));
}
}
vector <pair <int, int> > all(n);
for(int i = 0 ; i < n ; i++){
all[i] = make_pair(cnt[i], i);
}
vector <vector <int> > answer(n, vector <int>(m, -1));
vector <int> l(n), r(n, m - 1);
for(int i = 0 ; i < k ; i++){
sort(all.rbegin(), all.rend());
for(int j = 0 ; j < n ; j++){
int row = all[j].second;
if(j < n / 2){
answer[row][l[row]++] = i;
all[j].first--;
}
else{
answer[row][r[row]--] = i;
}
}
}
allocate_tickets(answer);
return res;
}
