#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
struct Item{
int x, i, j;
bool operator < (const Item &sc) const{
return array<int, 3>{x, i, j} < array<int, 3>{sc.x, sc.i, sc.j};
}
};
long long find_maximum(int k, vector<vector<int>> arr){
int n = arr.size();
int m = arr[0].size();
vector ans(n, vector(m, -1));
long long ansvalue = 0;
vector<Item> v;
for(int i = 0; i < n; i++){
for(int j = 0; j < k; j++){
ansvalue += arr[i][m - 1 - j];
}
}
for(int i = 0; i < n; i++){
for(int j = 0; j < k; j++){
v.push_back({arr[i][j] + arr[i][m - k + j], i, j});
}
}
sort(v.begin(), v.end());
vector zeros(n, vector<int>()), ones(n, vector<int>());
for(int i = 0; i < (n * k) / 2; i++){
ansvalue -= v[i].x;
zeros[v[i].i].push_back(v[i].j);
}
for(int i = (n * k) / 2; i < n * k; i++){
ones[v[i].i].push_back(m - k + v[i].j);
}
for(int i = 0; i < n; i++){
reverse(zeros[i].begin(), zeros[i].end());
reverse(ones[i].begin(), ones[i].end());
}
for(int i = 0; i < k; i++){
vector<pair<int, int>> v;
for(int j = 0; j < n; j++) v.push_back({zeros[j].size(), j});
sort(v.begin(), v.end(), greater<decltype(v[0])>());
for(int j = 0; j < n / 2; j++){
ans[v[j].second][zeros[v[j].second].back()] = i;
zeros[v[j].second].pop_back();
}
for(int j = n / 2; j < n; j++){
ans[v[j].second][ones[v[j].second].back()] = i;
ones[v[j].second].pop_back();
}
}
allocate_tickets(ans);
return ansvalue;
}
