#include "tickets.h"
#include <bits/stdc++.h>
using namespace std;
#define MAXN 301
#define MAXM 9001
#define nl '\n'
#define ff first
#define ss second
#define ll long long
#define ld long double
#define terminator main
#define pll pair<ll,ll>
#define add insert
#define append push_back
#define pii pair<int,int>
#define all(x) (x).begin(),(x).end()
int cnt[MAXN][2];
ll a[MAXN][MAXN];
pll dp[MAXN][MAXM];
bool vis[MAXN][MAXN];
ll find_maximum(int k, vector<vector<int>> x) {
int n, m, mx, o;
n = x.size();
m = x[0].size();
mx = n * k / 2;
for(int j = 0; j <= mx; j++)
dp[0][j] = {-1e18, -1e18};
dp[0][0] = {0, 0};
for(int i = 0; i < n; i++){
for(int j = 0; j < k; j++)
a[i][0] -= x[i][j];
for(int s = 0; s <= mx; s++)
dp[i + 1][s] = {dp[i][s].ff + a[i][0], 0};
for(ll j = 1; j <= k; j++){
a[i][j] = a[i][j - 1] + x[i][k - j] + x[i][m - j];
for(int s = 0; s <= mx - j; s++)
dp[i + 1][s + j] = max(dp[i + 1][s + j], {dp[i][s].ff + a[i][j], j});
}
}
ll ans = dp[n][mx].ff;
vector<vector<int>> v = x;
for(int i = 0; i < n; i++)
for(int j = 0; j < m; j++)
v[i][j] = -1;
vector<pair<int, pii>> u;
vector<int> w[2];
for(int i = n - 1; i >= 0; i--){
o = dp[i + 1][mx].ss;
for(int r = 0; r < k; r++){
u.append({cnt[r][0], {r, 0}});
u.append({cnt[r][1], {r, 1}});
}
for(int s = 0; s < k - o; s++)
w[0].append(s);
for(int s = m - o; s < m; s++)
w[1].append(s);
sort(all(u));
for(auto & r : u){
if(w[r.ss.ss].empty() || vis[r.ss.ff][i] == 1 || r.ff == n / 2 || v[i][w[r.ss.ss].back()] >= 0)
continue;
v[i][w[r.ss.ss].back()] = r.ss.ff;
cnt[r.ss.ff][r.ss.ss]++;
vis[r.ss.ff][i] = 1;
w[r.ss.ss].pop_back();
}
u.clear(), w[0].clear(), w[1].clear();
mx -= o;
}
allocate_tickets(v);
return ans;
}
