#include "tickets.h"
#include <vector>
#include <algorithm>
#include <queue>
using ll = long long;
class name {
public:
int i;
int cost;
bool operator<(const name& other) const{
return cost < other.cost;
}
};
class name2{
public:
int pos;
int value;
bool operator<(const name2& other) const {
return value < other.value;
}
};
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int N = x.size();
int M = x[0].size();
std::vector<std::vector<name2>> s(N,std::vector<name2>(M));
std::vector<std::vector<int>> ans(N,std::vector<int>(M,-1));
std::priority_queue<name> g;
for(int q = 0;q < N;q++) {
for(int w = 0;w < M;w++) {
s[q][w].value = x[q][w];
s[q][w].pos = w;
}
std::sort(s[q].begin(),s[q].end());
}
int off_set = M - k;
std::vector<int> group(N,0);
for(int q = 0;q < N;q++){
for(int w = 0;w < k;w++) {
name n;
n.cost = -x[q][M - 1 - w];
if(M - q - w - off_set >= 0) n.cost += -x[q][M - 1 - w - off_set];
n.i = q;
g.push(n);
}
}
for(int q = 0;q < k * N / 2;q++) {
name e = g.top();
g.pop();
group[e.i]++;
}
std::vector<std::vector<int>> round(k);
int r = 0;
ll res = 0;
for(int q = 0;q < N;q++) {
for(int w = 0;w < group[q];w++) {
round[r].push_back(s[q][w].value);
//res -= s[q][w].value;
ans[q][s[q][w].pos] = r;
r++;
r%=k;
}
int start_pos = r;
for(int w = 0;w < k - group[q];w++) {
round[r].push_back(s[q][M - w - 1].value);
//res += s[q][M - w - 1].value;
ans[q][s[q][M - w - 1].pos] = r;
r++;
r%=k;
}
r = start_pos;
}
for(int q = 0;q < k;q++) {
std::sort(round[q].begin(),round[q].end());
for(int w = 0;w < N / 2;w++) res -= round[q][w];
for(int w = N / 2;w < N ;w++) res += round[q][w];
}
allocate_tickets(ans);
return res;
}
