#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
#define en "\n"
using pii = pair<int, int>;
using vi = vector<int>;
using vvi = vector<vi>;
/*ll praw_ans;
void allocate_tickets(vvi ans, vvi x, int k) {
int n = sz(ans);
int m = sz(ans[0]);
f(i, 0, n) {
set<int> uz;
f(j, 0, m) {
if (ans[i][j] != -1) uz.insert(ans[i][j]);
}
if (sz(uz) != k) {
cout << "blad w tej samej rundzie ten sam kolor\n";
exit(0);
}
}
praw_ans = 0;
vvi wyn(k);
f(i, 0, n) {
f(j, 0, m) {
if (ans[i][j] == -1) continue;
wyn[ans[i][j]].pb(x[i][j]);
}
}
tv(we, wyn) {
sort(all(we));
f(i, 0, sz(we)/2) {
praw_ans += (we[sz(we) - 1 - i] - we[i]);
}
}
}*/
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
ll 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 += ll(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 n, m, k;
cin >> n >> m >> k;
vvi x(n, vi(m));
f(i, 0, n) {
f(j, 0, m) cin >> x[i][j];
}
int moj_ans = find_maximum(k, x);
if (praw_ans != moj_ans) {
cout << "blad rozne odpowiedzi\n";
} else {
cout << moj_ans << en;
}
}*/
