#include "tickets.h"
#include <vector>
#include <algorithm>
#include <iostream>
#include <queue>
#define ll long long
#define For(i, n) for(int i = 0; i < n; i++)
#define NEK 1000000000
#define vec vector
#define pii pair<int, int>
#define ff first
#define ss second
using namespace std;
ll vyrob_vysledok_z_pola(vec<pair<int, pii>>&p, int n, int m, int k){
For(i, p.size()){
cerr << p[i].ff << ' ';
}
cerr << endl;
sort(p.begin(), p.end());
ll sum = 0;
int kolo1 = 0;
vec<vec<int>> velkaci(n);
vec<vec<int>> odp(n, vec<int>(m, -1));
vec<vec<int>> bol(n, vec<int>(k, 0));
int polka = (n*k)/2;
For(i, polka){
sum += p[i+polka].ff;
int ja = p[i+polka].ss.ff;
int ja_listok = p[i+polka].ss.ss;
velkaci[ja].push_back({ja_listok});
}
cerr << "hafhaf" << endl;
For(i, velkaci.size()){
For(j, velkaci[i].size()){
odp[i][velkaci[i][j]] = kolo1;
bol[i][kolo1] = 1;
kolo1++;
if(kolo1 == k) kolo1 -= k;
}
}
vec<int> pos(n, 0);
vec<int> poc(k, polka);
For(i, polka){
sum -= p[i].ff;
int ja = p[i].ss.ff;
int ja_listok = p[i].ss.ss;
while(bol[ja][pos[ja]] || poc[pos[ja]] == 0) pos[ja]++;
odp[ja][ja_listok] = pos[ja];
poc[pos[ja]]--;
pos[ja]++;
}
allocate_tickets(odp);
return sum;
}
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n = x.size();
int m = x[0].size();
int poc1 = 0;
vec<int> p1(n, 0), p2(n, m-k);
priority_queue<pii> q;
For(i, n){
q.push({(-1) * (x[i][p2[i]] + x[i][p1[i]]), i});
cerr << "i: " << i << " suc: " << (x[i][p2[i]] - x[i][p1[i]]) << endl;
}
int polka = (n*k)/2;
For(i, polka){
ll w = q.top().ss; q.pop();
p1[w]++; p2[w]++;
if(p2[w] >= x[w].size()) continue;
q.push({(-1) * (x[w][p2[w]] - x[w][p1[w]]), w});
}
cerr << "som tu" << endl;
vec<pair<int, pii>> p;
For(i, n){
for(int j = 0; j < p1[i]; j++){
cerr << i << ' ' << j << "tata" << endl;
p.push_back({x[i][j], {i, j}});
}
for(int j = p2[i]; j < m; j++){
cerr << i << ' ' << j << endl;
p.push_back({x[i][j], {i, j}});
}
}
cerr << "baf" << endl;
return vyrob_vysledok_z_pola(p, n, m, k);
}
