#include "tickets.h"
#include <algorithm>
#include <iostream>
#include <cassert>
#include <numeric>
#include <vector>
#include <queue>
typedef long long llong;
const int MAXN = 1500 + 10;
const int INF = 1e9;
int n, m;
int t[MAXN][MAXN];
int ans[MAXN][MAXN];
int perm[MAXN][MAXN];
std::priority_queue <std::pair <int,int>> pq;
int usedMAX[MAXN];
int usedMIN[MAXN];
int sorted[MAXN];
long long find_maximum(int k, std::vector<std::vector<int>> x)
{
n = x.size();
m = x[0].size();
llong ans = 0;
for (int i = 1 ; i <= n ; ++i)
{
for (int j = 1 ; j <= m ; ++j)
{
t[i][j] = x[i - 1][j - 1];
perm[i][j] = j;
}
std::sort(perm[i] + 1, perm[i] + 1 + m, [&](int x, int y)
{
return t[i][x] < t[i][y];
});
for (int j = 1 ; j <= k ; ++j)
{
ans -= t[i][perm[i][j]];
}
usedMIN[i] = k;
usedMAX[i] = m;
pq.push({t[i][perm[i][usedMAX[i]]] + t[i][perm[i][usedMIN[i]]], i});
}
for (int flips = 1 ; flips <= n * k / 2 ; ++flips)
{
auto [value, idx] = pq.top();
pq.pop();
ans += value;
usedMIN[idx]--;
usedMAX[idx]--;
if (usedMIN[idx] > 0)
{
pq.push({t[idx][perm[idx][usedMAX[idx]]] + t[idx][perm[idx][usedMIN[idx]]], idx});
}
}
std::vector <std::vector <int>> answer(n);
for (int i = 0 ; i < n ; ++i)
{
answer[i].resize(m, -1);
}
std::iota(sorted + 1, sorted + 1 + n, 1);
for (int round = 0 ; round < k ; ++round)
{
std::sort(sorted + 1, sorted + 1 + n, [&](int x, int y)
{
return usedMAX[x] < usedMAX[y];
});
for (int i = 1 ; i <= n / 2 ; ++i)
{
usedMAX[sorted[i]]++;
answer[sorted[i] - 1][perm[sorted[i]][usedMAX[sorted[i]]] - 1] = round;
}
for (int i = n / 2 + 1 ; i <= n ; ++i)
{
answer[sorted[i] - 1][perm[sorted[i]][usedMIN[sorted[i]]] - 1] = round;
usedMIN[sorted[i]]--;
}
}
allocate_tickets(answer);
return ans;
}
