#include "tickets.h"
#include <vector>
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
#include "/home/eagle/ioi19/day2/debug.h"
#else
#define debug(...) void(37)
#endif
long long find_maximum(int K, std::vector<std::vector<int>> X) {
int N = int(X.size());
int M = int(X[0].size());
long long ans = 0;
for (int i = 0; i < N; ++i) {
for (int j = 0; j < K; ++j) {
ans += X[i][M - 1 - j];
}
}
priority_queue<pair<int, int>> pq;
vector<int> pt(N);
for (int i = 0; i < N; ++i) {
pq.emplace(-X[i][0] - X[i][M - K], i);
}
int half = N * K / 2;
while (half--) {
auto[add, i] = pq.top();
pq.pop();
ans += add;
++pt[i];
if (pt[i] < K) {
pq.emplace(-X[i][pt[i]] - X[i][M - K + pt[i]], i);
}
}
assert(accumulate(pt.begin(), pt.end(), 0) == N * K / 2);
vector<int> big_pt(N);
for (int i = 0; i < N; ++i) {
big_pt[i] = K - pt[i];
}
vector<vector<int>> s(N, vector<int>(M, -1));
for (int t = 0; t < K; ++t) {
vector<int> bigs, smalls;
vector<bool> used(N);
for (int i = 0; i < N; ++i) {
used[i] = true;
if (pt[i] == K - t) {
--pt[i];
s[i][pt[i]] = t;
smalls.push_back(X[i][pt[i]]);
} else if (big_pt[i] == K - t) {
s[i][M - big_pt[i]] = t;
bigs.push_back(X[i][M - big_pt[i]]);
--big_pt[i];
} else {
used[i] = false;
}
}
for (int i = 0; i < N; ++i) {
if (used[i]) continue;
if (pt[i] > 0 && int(smalls.size()) < N / 2) {
--pt[i];
s[i][pt[i]] = t;
smalls.push_back(X[i][pt[i]]);
} else {
s[i][M - big_pt[i]] = t;
bigs.push_back(X[i][M - big_pt[i]]);
--big_pt[i];
}
}
assert(int(smalls.size()) <= N / 2);
assert(*max_element(smalls.begin(), smalls.end()) <= *min_element(bigs.begin(), bigs.end()));
}
allocate_tickets(s);
debug(ans);
return ans;
}
