#include <bits/stdc++.h>
typedef long long ll;
typedef unsigned long long ull;
void allocate_tickets(std::vector <std::vector <int>> s);
struct cmp {
bool operator()(const std::pair <int, int>& a, const std::pair <int, int>& b) const {
if (a.first == b.first) return a.second < b.second;
return a.first > b.first;
}
};
std::vector <std::pair <int, int>> ptr;
int n, m;
bool mcmp(const int& a, const int& b) {
return ptr[a].second < ptr[b].second;
}
ull find_maximum(int k, std::vector <std::vector <int>> x) {
n = x.size();
m = x[0].size();
for (auto& v : x) {
std::reverse(v.begin(), v.end());
}
ll r = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < k; j++) {
r += x[i][j];
}
}
ptr.resize(n, { k - 1, m });
std::set <std::pair <int, int>, cmp> st;
for (int i = 0; i < n; i++) {
st.insert({ - x[i][ptr[i].first] - x[i][ptr[i].second - 1], i });
}
for (int i = 0; i < (n * k) >> 1; i++) {
r += st.begin()->first;
auto p = *st.begin();
st.erase(st.begin());
ptr[p.second].first--;
ptr[p.second].second--;
if (ptr[p.second].first < 0) continue;
st.insert({ - x[i][ptr[i].first] - x[i][ptr[i].second - 1], p.second });
}
for (int i = 0; i < n; i++) {
std::cout << "(" << ptr[i].first << " ; " << ptr[i].second << ")" << std::endl;
}
std::vector <std::vector <int>> ans(n, std::vector <int> (m, -1));
for (int i = 0; i < k; i++) {
std::vector <int> now(n);
std::iota(now.begin(), now.end(), 0);
std::sort(now.begin(), now.end(), mcmp);
for (int j = 0; j < n >> 1; j++) {
ans[now[j]][ptr[now[j]].second++] = i;
}
for (int j = n >> 1; j < n; j++) {
ans[now[j]][ptr[now[j]].first--] = i;
}
}
for (auto& v : ans) {
std::reverse(v.begin(), v.end());
}
allocate_tickets(ans);
return r;
}
