#include "tickets.h"
#include <bits/stdc++.h>
#define fr(i, a, b) for(int i = a; i <= b; i++)
#define rf(i, a, b) for(int i = a; i >= b; i--)
#define fe(x, y) for (auto& x : y)
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define pw(x) (1LL << (x))
#define sz(x) (int)x.size()
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
#define fbo find_by_order
#define ook order_of_key
template <typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template <typename T>
using ve = vector <T>;
template <typename T>
bool umx (T& a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T>
bool umn (T& a, T b) { return a > b ? a = b, 1 : 0; }
using ll = long long;
using ld = long double;
using pll = pair <ll, ll>;
using pii = pair <int, int>;
using ull = unsigned long long;
const int oo = 1e9;
const ll OO = 1e18;
const int N = 1e6 + 10;
const int M = 3e3 + 100;
const int mod = 1e9 + 7;
ll dp[M][M];
int p[M][M];
int cnt[M][2];
ve <int> ones[M];
ve <int> zero[M];
set <int> can[M];
long long find_maximum(int k, std::vector<std::vector<int>> x) {
int n = x.size();
int m = x[0].size();
ve <ve <int>> A = x;
set <pair <int, int>> ST;
for (int i = 0; i < n; i++) ST.insert({cnt[i][1], i});
ve <int> used(n, 0);
ll ans = 0;
std::vector<std::vector<int>> answer;
for (int i = 0; i < n; i++) {
std::vector<int> row(m);
for (int j = 0; j < m; j++) row[j] = -1;
answer.push_back(row);
}
ve <array <int, 3>> V;
for (int i = 0; i < n; i++) {
for (int j = 0; j < k; j++) {
V.pb({x[i][j] + x[i][m - k + j], i, j});
}
for (int j = m - k; j < m; j++) ans += x[i][j];
}
sort(all(V));
set <pii> cnt;
ve <int> need(n, 0);
ve <ve <int>> have(n);
for (int i = 0; i < k; i++) cnt.insert({0, i});
for (int i = 0; i < k * n / 2; i++) {
ans -= V[i][0];
need[V[i][1]]++;
have[V[i][1]].pb(V[i][2]);
}
for (int i = 0; i < n; i++) {
int nd = need[i];
ve <pii> Z;
while(sz(Z) < nd) {
auto [x, id] = *cnt.begin();
cnt.erase(cnt.begin());
Z.pb({x + 1, id});
}
fe (x, Z) {
cnt.insert(x);
answer[i][have[i].back()] = x.se;
have[i].pop_back();
}
}
for (int i = 0; i < n; i++) {
set <int> can;
for (int j = 0; j < k; j++) can.insert(j);
for (int j = 0; j < m; j++) {
if (answer[i][j] != -1) can.erase(answer[i][j]);
}
for (int j = m - 1; j >= 0; j--) {
if (!sz(can)) break;
answer[i][j] = *can.begin();
can.erase(can.begin());
}
}
allocate_tickets(answer);
return ans;
}
