#include "tickets.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
void allocate_tickets(vector<vector<int>> _d) ;
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n = x.size();
int m = x[0].size();
vector<std::vector<int>> answ(n , vector<int> (m , -1));
vector<pair<int , pair<int , int>>> vc;
set<int> st[n];
for(int i = 0;i < n; ++ i){
for(int j = m - 1;j >= m - k; -- j){
st[i].insert(m - 1 - j);
vc.push_back({x[i][j] + x[i][j - m + k] , {i , j}});
}
//cout << '\n';
}
// авававааавава
sort(vc.rbegin() , vc.rend());
long long ans = 0;
vector<int> ps(n , m) , f(k + 1 , 0) , d(n , 0);
vector<int> pq;
for(int i = 0;i < (n / 2) * k; ++ i){
ans += x[vc[i].se.fi][vc[i].se.se];
//cout << vc[i].se.fi << ' ' << vc[i].se.se << '\n';
pq.push_back(vc[i].se.fi);
}
sort(pq.begin() , pq.end());
int kol = 0;
for(auto i : pq){
ps[i] --;
int p = ps[i];
int day = kol % k;
kol ++;
answ[i][p] = day;
st[i].erase(day);
}
reverse(vc.begin() , vc.end());
vector<int> pos(n , 0);
for(int i = 0;i < (n / 2) * k; ++ i){
int p = pos[vc[i].se.fi];
pos[vc[i].se.fi] ++;
ans -= x[vc[i].se.fi][p];
// cout << vc[i].se.fi << ' ' << p << '\n';
answ[vc[i].se.fi][p] = *(st[vc[i].se.fi].begin());
st[vc[i].se.fi].erase(st[vc[i].se.fi].begin());
}
allocate_tickets(answ);
return ans;
}
