#include "tickets.h"
#include <bits/stdc++.h>
#define ALL(X) begin(X), end(X)
namespace {
using i64 = long long;
using namespace std;
template <class T>
using vec = vector<T>;
template <class T>
istream& operator>>(istream& is, vec<T>& X) {
for (auto& x : X) {
is >> x;
}
return is;
}
template <class T>
constexpr T infty = 0;
template <>
constexpr int infty<int> = 1'000'000'000;
template <>
constexpr i64 infty<i64> = 1'000'000'000'000'000'000;
}
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int N = size(x);
int M = size(x[0]);
vec<int> id(N);
priority_queue<pair<int, int>> pq;
i64 sum{};
for (int i = 0; i < N; i++) {
for (int j = M - k; j < M; j++) {
sum += x[i][j];
}
pq.emplace(-x[i][0] - x[i][M - k], i);
}
for (int t = N * k / 2; t--; ) {
auto [v, i] = pq.top(); pq.pop();
sum += v;
if (++id[i] < k) {
pq.emplace(-x[i][id[i]] - x[i][M - k + id[i]], i);
}
}
vec<vec<int>> answer(N, vec<int>(M, -1));
vec<int> ord(N), id2(N);
iota(ALL(ord), 0);
for (int i = 0; i < N; i++) {
id2[i] = M - k + id[i];
}
for (int t = 0; t < k; t++) {
sort(ALL(ord), [&](int i, int j) {
return id[i] > id[j];
});
for (int i = 0; i < N / 2; i++) {
int j = ord[i];
assert(id[j] > 0);
answer[j][--id[j]] = t;
}
for (int i = N / 2; i < N; i++) {
int j = ord[i];
assert(id2[j] < M);
answer[j][id2[j]++] = t;
}
}
allocate_tickets(answer);
return sum;
}
