#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
template<typename T>
using vec = vector<T>;
#define i32 int32_t
#define int long long
#define len(x) ((int)(x).size())
long long find_maximum(i32 k, std::vector<std::vector<i32>> x) {
int n = x.size();
int m = x[0].size();
vec<vec<i32>> d(n, vec<i32>(m, -1));
// allocate_tickets(vec<vec<i32>>(n, vec<i32>(m, 0)));
int S = 0;
set<pair<int, int>> deltas;
vec<int> ptr(n, 0);
for (int i = 0; i < n; i++) {
for (int j = m - k; j < m; j++) {
S += x[i][j];
}
deltas.emplace(-x[i][m - k + ptr[i]] - x[i][ptr[i]], i);
// deltas.emplace(-x[i].back() - x[i][0], i);
}
for (int t = 0; t < n * k / 2; t++) {
auto [xy, i] = *deltas.rbegin();
deltas.erase(prev(deltas.end()));
S += xy;
d[i][m - k + ptr[i]] = -1;
ptr[i]++;
if (ptr[i] < k) {
deltas.emplace(-x[i][m - k + ptr[i]] - x[i][ptr[i]], i);
}
}
// vec<pair<int, int>> mins;
// vec<pair<int, int>> maxs;
// for (int i = 0; i < n; i++) {
// for (int j = 0; j < m; j++) {
// if (d[i][j] == 1) {
// mins.emplace_back(i, j);
// } else if (d[i][j] == -1) {
// maxs.emplace_back(i, j);
// }
// }
// }
vec<int> bd(n, 0);
for (int t = 0; t < k; t++) {
vec<int> ids(n);
iota(ids.begin(), ids.end(), 0);
sort(ids.rbegin(), ids.rend(), [&](int i, int j) {
return ptr[i] < ptr[j];
});
for (int i = 0; i < n / 2; i++) {
d[ids[i]][ptr[ids[i]]-1] = t;
ptr[ids[i]]--;
}
for (int i = n / 2; i < n; i++) {
d[ids[i]][m - 1 - bd[ids[i]]] = t;
bd[ids[i]]++;
}
}
allocate_tickets(d);
return S;
}
