#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1.5e3 + 20;
vector<int> pos[maxn];
vector<int> neg[maxn];
int cnt[maxn];
int n, m, k;
void trace() {
vector<vector<int>> res(n, vector<int>(m, -1));
for (int i = 0; i < n; i++) {
for (int j = 0; j < cnt[i]; j++) {
pos[i].push_back(m - 1 - j);
}
for (int j = 0; j < k - cnt[i]; j++) {
neg[i].push_back(j);
}
}
for (int i = 0; i < k; i++) {
int rem = n / 2;
for (int j = 0; j < n; j++) {
if (neg[j].empty()) {
res[j][pos[j].back()] = i;
pos[j].pop_back();
rem--;
}
}
for (int j = 0; j < n; j++) {
if (!neg[j].empty()) {
if (pos[j].empty() || rem == 0) {
res[j][neg[j].back()] = i;
neg[j].pop_back();
}
else {
res[j][pos[j].back()] = i;
pos[j].pop_back();
rem--;
}
}
}
}
allocate_tickets(res);
}
long long find_maximum(int _k, vector<vector<int>> a) {
n = a.size();
m = a[0].size();
k = _k;
vector<pair<int, int>> cost;
long long res = 0;
for (int i = 0; i < n; i++) {
for (int j = 1; j <= k; j++) {
res -= a[i][j - 1];
cost.emplace_back(a[i][k - j] + a[i][m - j], i);
}
}
sort(cost.begin(), cost.end(), greater<pair<int, int>>());
for (int i = 0; i < n / 2 * k; i++) {
res += cost[i].first;
cnt[cost[i].second]++;
}
trace();
return res;
}
