#include "tickets.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx,avx2")
using namespace std;
using i32 = int;
#define int long long
#define len(x) (int)(x.size())
#define all(x) x.begin(), x.end()
template<typename T>
using vec = vector<T>;
const int maxN = 305;
const int maxK = 305;
int dp[maxN][maxN * maxK / 2];
int mv[maxN][maxN * maxK / 2];
long long find_maximum(i32 k, vector<vector<i32>> d) {
int n = len(d);
int m = len(d[0]);
vec<int> cnt(n, m);
int ans = 0;
// memset(dp, -1000'000'000'000'000'00LL, sizeof dp);
memset(mv, -1, sizeof mv);
for(int i=0;i<=n;i++){
for(int j=0;j<n*k/2;j++){
dp[i][j] = -1e17;
}
}
// vec<vec<int>> dp(n + 1, vec<int>(n * k / 2 + 1, -1e17));
// vec<vec<int>> move(n + 1, vec<int>(n * k / 2 + 1, -1));
dp[0][0] = 0;
for (int i = 1; i <= n; i++) {
int sums = 0;
for (int j = m - 1; j >= m - k; j--) {
sums += d[i - 1][j];
}
for (int j = k; j >= 0; j--) {
for (int l = 0; l <= min(n * k / 2, i * k) - j; l++) {
if (dp[i - 1][l] + sums >= dp[i][l + j]) {
dp[i][l + j] = dp[i - 1][l] + sums;
mv[i][l + j] = j;
}
}
if (j != 0) {
sums -= d[i - 1][m - k + (k - j)];
sums -= d[i - 1][k - j];
}
}
}
ans = dp[n][n * k / 2];
int cur = n * k / 2;
for (int i = n; i > 0; i--) {
cnt[i - 1] = mv[i][cur];
cur -= mv[i][cur];
}
{
vec<vec<i32>> ops(n, vec<i32>(m, -1));
vec<int> from_bot(n, 0);
for (int t = 0; t < k; t++) {
vec<int> ids(n);
iota(all(ids), 0);
sort(all(ids), [&](int a, int b) {
return cnt[a] < cnt[b];
});
for (int i = 0; i < n / 2; i++) {
int id = ids[i];
int pos = from_bot[id];
assert(0 <= pos and pos < m);
ops[id][pos] = t;
from_bot[id]++;
}
for (int i = n / 2; i < n; i++) {
int id = ids[i];
int pos = t - from_bot[id];
ops[id][m - pos - 1] = t;
cnt[id]--;
}
}
allocate_tickets(ops);
}
return ans;
}
