#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;
for(int i = 0;i < n; ++ i){
for(int j = n - 1;j >= n - k; -- j){
vc.push_back({x[i][j] + x[i][j - n + k] , {i , j}});
}
//cout << '\n';
}
sort(vc.rbegin() , vc.rend());
long long ans = 0;
vector<int> cnt(n , 0);
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';
answ[vc[i].se.fi][vc[i].se.se] = cnt[vc[i].se.fi];
cnt[vc[i].se.fi] ++;
}
reverse(vc.begin() , vc.end());
vector<int> ps(n , 0);
for(int i = 0;i < (n / 2) * k; ++ i){
int p = ps[vc[i].se.fi];
ps[vc[i].se.fi] ++;
ans -= x[vc[i].se.fi][p];
answ[vc[i].se.fi][p] = cnt[vc[i].se.fi];
cnt[vc[i].se.fi] ++;
}
allocate_tickets(answ);
return ans;
}
