#include <bits/stdc++.h>
#include "tickets.h"
using namespace std;
typedef long long ll;
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
#define sz(a) int(a.size())
#define f(i, a, b) for (int i = a; i < b; i++)
#define rep(i, a) f(i, 0, a)
#define tv(a, x) for (auto& a : x)
#define DUZO 1000000000000000000LL
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
/*void allocate_tickets(vvi ans) {
int n = sz(ans);
int m = sz(ans[0]);
cout << "moja odpowiedz to:\n";
rep(i, n) {
rep(j, m) {
cout << ans[i][j] << " ";
}
cout << "\n";
}
}*/
ll find_maximum(int k, vvi x) {
int n = sz(x);
int m = sz(x[0]);
//wybieramy k * n/2 najlepszych i najgorszych
vvi ans(n, vi(m, -1));
priority_queue<pii> najw;
vi wsk(n, m - 1);
rep(i, n) najw.push({x[i].back(), i});
vi ile(k, 0); //ile juz wzielo udzial
int sum1 = 0;
rep(_, (k * n)/2) {
pii p1 = najw.top();
int ind = p1.nd;
sum1 += p1.st;
najw.pop();
wsk[ind]--;
if (wsk[ind] >= (m - k)) najw.push({x[ind][wsk[ind]], ind});
}
vector<pii> wzielismy(n);
f(i, 0, n) wzielismy[i] = {(m - 1) - wsk[i], i};
sort(all(wzielismy));
reverse(all(wzielismy));
priority_queue<pii> wolny; //ile wolnych miejsc
f(i, 0, k) wolny.push({k/2, i});
tv(ele, wzielismy) {
vi uzyte;
f(j, 0, ele.st) {
pii p1 = wolny.top();
wolny.pop();
int ind = p1.nd;
ile[ind]++;
ans[ele.nd][m - 1 - j] = ind + 1;
if (ile[ind] < (n/2)) {
uzyte.pb(ind);
}
}
tv(l, uzyte) {
wolny.push({(k/2) - ile[l], l});
}
}
priority_queue<pii> najm;
f(i, 0, n) wsk[i] = 0;
rep(i, n) najm.push({-x[i][0], i});
f(i, 0, k) ile[i] = 0;
vi ost(k, 0); //ostatin element w naszym bloku
int sum2 = 0;
rep(_, (k * n)/2) {
pii p1 = najm.top();
sum2 = p1.st;
int ind = p1.nd;
najm.pop();
wsk[ind]++;
if (wsk[ind] < (k - 1)) najm.push({-x[ind][wsk[ind]], ind});
}
f(i, 0, n) wzielismy[i] = {wsk[i], i};
sort(all(wzielismy));
reverse(all(wzielismy));
wolny = {};
f(i, 0, k) wolny.push({(k/2), i});
f(i, 0, k) ile[i] = 0;
tv(ele, wzielismy) {
vi uzyte;
f(j, 0, ele.st) {
pii p1 = wolny.top();
wolny.pop();
int ind = p1.nd;
ile[ind]++;
ans[ele.nd][j] = ind + 1;
if (ile[ind] < (n/2)) {
uzyte.pb(ind);
}
}
tv(l, uzyte) {
wolny.push({(k/2) - ile[l], l});
}
}
int wnk = sum1 + sum2; //sum2 na minusie wiec essa
allocate_tickets(ans);
return wnk;
}
/*int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int k = 2;
//[[0, 2, 5],[1, 1, 3]]
vvi x = {{0, 0, 2}, {0, 0, 2}, {0, 1, 1}, {0, 0, 0}};
int moj_ans = find_maximum(k, x);
cout << "moja odpowiedz to " << moj_ans << "\n";
}*/
