#include "tickets.h"
#include <vector>
#include<iostream>
#include<algorithm>
#include<utility>
#include<queue>
using namespace std;
typedef long long ll;
long long find_maximum(int k, std::vector<std::vector<int>> xx) {
int n = (int)xx.size();
int m = (int)xx[0].size();
vector<vector<ll>> vec(n, vector<ll>(m));
for(int i = 0; i < n; i++) for(int j = 0; j < m; j++) vec[i][j] = xx[i][j];
vector<vector<int>> ans(n, vector<int>(m, -1));
vector<int> l(n, 0), r(n, m - k);
priority_queue<pair<ll, int>> pq;
ll sum = 0;
for(int i = 0; i < n; i++){
for(int j = m - k; j < m; j++){
sum += vec[i][j];
}
pq.emplace(-vec[i][m - k] - vec[i][0], i);
}
int times = n * k / 2;
for(int i = 0; i < times; i++){
auto [val, id] = pq.top();
//cout << val << " " << id << '\n';
pq.pop();
sum += val;
l[id]++;
r[id]++;
if(r[id] < m){
pq.emplace(-vec[i][r[id]] - vec[i][l[id]], id);
}
}
vector<pair<pair<int, int>, int>> srtd;
for(int i = 0; i < n; i++){
srtd.emplace_back(make_pair(l[i] - 1, r[i]), i);
}
for(int rnd = 0; rnd < k; rnd++){
sort(srtd.begin(), srtd.end());
for(int i = 0; i < n / 2; i++){
int id = srtd[i].second;
auto &[l, r] = srtd[i].first;
ans[id][r] = rnd;
r++;
}
for(int i = n / 2; i < n; i++){
int id = srtd[i].second;
auto &[l, r] = srtd[i].first;
ans[id][l] = rnd;
l--;
}
}
allocate_tickets(ans);
return sum;
}
// g++ -std=c++17 -Wall -Wextra -Wshadow -fsanitize=undefined -fsanitize=address -o run -g grader.cpp tickets.cpp
