#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][wsk[i]] + x[i][k - (m - wsk[i])], i});
vi ile(k, 0); //ile juz wzielo udzial
int wnk = 0;
f(i, 0, n) f(j, 0, k) wnk -= x[i][j];
rep(_, (k * n)/2) {
pii p1 = najw.top();
int ind = p1.nd;
wnk += p1.st;
najw.pop();
wsk[ind]--;
if (wsk[ind] >= (m - k)) najw.push({x[ind][wsk[ind]] + x[ind][k - (m - 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;
//cout << "Git\n";
if (ile[ind] < (n/2)) {
uzyte.pb(ind);
}
}
tv(l, uzyte) {
wolny.push({(k/2) - ile[l], l});
}
}
f(i, 0, n) {
set<int> dozw;
f(i, 0, k) dozw.insert(i);
for (int j = m - 1; j >= 0; j--) {
if (ans[i][j] != -1) dozw.erase(ans[i][j]);
}
auto it = dozw.begin();
f(j, 0, sz(dozw)) {
ans[i][j] = *it;
it = next(it);
}
}
allocate_tickets(ans);
return wnk;
}
/*int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int k = 1;
vvi x = {{5, 9}, {1, 4}, {3, 6}, {2, 7}};
//[[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";
}*/
